What is the brute force approach and complexity for Decode Ways?

Recursive ways(i): add the one-digit cut if valid, add the two-digit cut if valid, with no memory with time complexity O(2^N) and space complexity O(N).

Decode Ways

Q: How do you identify the pattern for Decode Ways?

Look for key signals in the prompt: "number of ways to decode" indicates The question asks for a count of cuts, not the cuts themselves. Build the count one prefix at a time.; "a piece is 1 to 26" indicates Each piece is one or two characters long, so the count for prefix i depends only on prefixes i − 1 and i − 2.; "leading zeros are not allowed" indicates Not every piece counts. Each choice needs a check, and a 0 can only be used as the second digit of a valid pair..

Medium·LeetCode #91 Pro OnlySlight Variation

LeetCode

Problem Statement

A message is written as a string of digits. The code is: 1 means A, 2 means B, and so on up to 26 for Z.

To read the message, you cut the digit string into pieces, and each piece is read as one letter. Count the different ways to cut the whole string into valid pieces.

A piece is valid only when its value is 1 to 26. So a lone 0 is not valid, and a piece with a leading zero, like 06, is not valid either. If no way to cut the string works, the answer is 0.

Input

A string s of digits.

Output

The number of ways to cut s into valid pieces. Return 0 when no cut works.

Example 1

Input: s = "12"

Output: 2

Two ways: 1 | 2 gives AB, and 12 gives L.

Example 2

Input: s = "226"

Output: 3

Three ways: 2 | 2 | 6 gives BBF, 2 | 26 gives BZ, and 22 | 6 gives VF.

Example 3

Input: s = "06"

Output: 0

The cuts are 0 | 6 and 06. Neither works: 0 is not a code, and 06 has a leading zero.

Constraints

• 1 ≤ s.length ≤ 100
• s contains only digits and may contain leading zeros.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“number of ways to decode”

→ The question asks for a count of cuts, not the cuts themselves. Build the count one prefix at a time.

“a piece is 1 to 26”

→ Each piece is one or two characters long, so the count for prefix i depends only on prefixes i − 1 and i − 2.

“leading zeros are not allowed”

→ Not every piece counts. Each choice needs a check, and a 0 can only be used as the second digit of a valid pair.

Approach Complexity Ladder

Brute Force — plain recursion on the last pieceO(2^N)O(N)

Recursive ways(i): add the one-digit cut if valid, add the two-digit cut if valid, with no memory

Better — memoization (remember the count for each prefix)O(N)O(N)

The same recursion, storing each ways(i) the first time it is computed

Optimal — two values, sliding along the stringO(N)O(1)

Keep the counts for the last two prefixes in two variables, and slide them forward one character at a time

Brute Force Intuition

Let ways(i) be the number of ways to decode the first i characters. Its last piece is either the single character s[i − 1], or the two characters s[i − 2] and s[i − 1]. Each choice is added only when it is a valid code. The recursion is correct, but the same prefix is asked for again and again, so it grows very fast.

Recognition rule for this sub-pattern:

dp[i] depends on dp[i−1] and dp[i−2]; keep just two variables.

Remember this · DP — 1D Linear

Trigger

"Number of ways", "maximum/minimum up to i", choices at each step that depend on the previous one or two.

Think

If I knew the answer for every smaller prefix, how would I get the answer for i?

Key question

What does dp[i] mean in one sentence?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — 1D Linear translate into production architectures and low-level memory mechanics.

LLD Architecture