Decode Ways

At every position in the string, you have a choice:

• Take the current digit as a single-digit code (if it is not '0'), and recursively count the number of ways to decode the rest of the string starting from the next index.
• Take the current digit and the next digit together as a two-digit code (if they form a number between 10 and 26), and recursively count the number of ways to decode the rest starting two positions ahead.

The total number of decodings from the current position is the sum of the decodings from both choices.

This is essentially a decision tree. At each position, you branch into one or two paths. The base case is when you reach the end of the string — that means you have found one valid decoding, so you return 1.

Think of it like reading a sentence where some words overlap. At each point, you can read one letter or two letters, and you want to count how many different readings are possible. You try every possibility by exploring all branches.

The problem with this approach is that it recomputes the same subproblems over and over. For example, decode(i+1) might be computed from multiple different positions, leading to exponential time.

Let's trace with s = "226":

Step 1: Start at index 0. s[0]='2' ≠ '0', so we can take it as a single digit.

• Branch A: Decode '2' as 'B', recurse on "26" (index 1)
• s[0..1]="22", 22 ≤ 26, so we can also take two digits.
• Branch B: Decode '22' as 'V', recurse on "6" (index 2)

Step 2 (Branch A): At index 1, s[1]='2' ≠ '0'.

• Branch A1: Decode '2' as 'B', recurse on "6" (index 2)
• s[1..2]="26", 26 ≤ 26, valid two-digit.
• Branch A2: Decode '26' as 'Z', recurse on "" (index 3)

Step 3 (Branch A1): At index 2, s[2]='6' ≠ '0'.

• Decode '6' as 'F', recurse on "" (index 3)
• Index 3 == length → base case, return 1.
• No two-digit option (would go past end).
• Result: 1 → This gives decoding "B" + "B" + "F" = "BBF"

Step 4 (Branch A2): Index 3 == length → return 1.

• This gives decoding "B" + "Z" = "BZ"

Step 5 (Branch A total): 1 + 1 = 2

Step 6 (Branch B): At index 2, s[2]='6' ≠ '0'.

• Decode '6' as 'F', recurse on "" (index 3) → return 1.
• This gives decoding "V" + "F" = "VF"

Step 7 (Branch B total): 1

Step 8 (Final): Branch A (2) + Branch B (1) = 3

1. Define a recursive function decode(s, index)
2. Base case: If index >= s.length, return 1 (one valid decoding found)
3. Invalid case: If s[index] == '0', return 0 (a '0' cannot be decoded alone)
4. Single digit: Count ways = decode(s, index + 1)
5. Two digits: If index + 1 < s.length and the two-digit number s[index..index+1] is between 10 and 26, add decode(s, index + 2) to ways
6. Return ways
7. Call decode(s, 0) as the answer

Time Complexity: O(2^n)

At each index, we make up to 2 recursive calls (one for single digit, one for two digits). This creates a binary recursion tree of depth n. In the worst case (e.g., a string of all '1's like "1111..."), every position branches twice, leading to 2^n total calls.

Space Complexity: O(n)

The recursion stack can go at most n levels deep (one level per character in the string). No additional data structures are used.

The recursive structure is perfect — the only problem is redundant computation. The fix is simple: cache the result of each decode(i) so we never compute it twice.

We use a memoization array (or hash map) where memo[i] stores the number of decodings for the substring starting at index i. Before computing decode(i), we check if memo[i] already has a value. If it does, we return it immediately. If not, we compute it, store it, and return it.

This transforms the recursion tree into a directed acyclic graph (DAG) — each unique subproblem is solved exactly once, and its result is reused by any parent that needs it.

The recursion still works top-down (from index 0 toward the end), but with memoization, we ensure each index is processed only once, giving us O(n) time.

Let's trace with s = "226", using memo array initialized to -1:

Step 1: Call decode(0). memo[0] == -1, not cached. s[0]='2' ≠ '0'.

• Single: call decode(1)
• Two-digit: "22" ≤ 26 → call decode(2)

Step 2: Call decode(1). memo[1] == -1. s[1]='2' ≠ '0'.

• Single: call decode(2)
• Two-digit: "26" ≤ 26 → call decode(3)

Step 3: Call decode(2). memo[2] == -1. s[2]='6' ≠ '0'.

• Single: call decode(3). Index 3 ≥ length → return 1.
• No valid two-digit (past end).
• memo[2] = 1. Return 1.

Step 4: Call decode(3). Index 3 ≥ length → return 1.

Step 5: Back in decode(1): single = decode(2) = 1 (from cache!), two-digit = decode(3) = 1.

• memo[1] = 1 + 1 = 2. Return 2.

Step 6: Back in decode(0): single = decode(1) = 2, two-digit = decode(2) = 1 (from cache!).

• memo[0] = 2 + 1 = 3. Return 3.

Notice: decode(2) was called from both decode(1) and decode(0), but only computed once — the second call was a cache hit.

1. Create a memoization array memo of size n+1, initialized to -1
2. Define decode(index):
   • If index >= n, return 1
   • If s[index] == '0', return 0
   • If memo[index] != -1, return memo[index] (cached result)
   • Compute ways = decode(index + 1) (single digit)
   • If two-digit s[index..index+1] is between 10 and 26, add decode(index + 2)
   • Store memo[index] = ways
   • Return ways
3. Return decode(0)

Time Complexity: O(n)

Each of the n subproblems (decode(0), decode(1), ..., decode(n-1)) is computed at most once. Each computation does O(1) work (checking characters and making two lookups). So the total time is O(n).

Space Complexity: O(n)

We use a memoization array of size n to store the results. Additionally, the recursion stack can go up to n levels deep in the worst case. So total space is O(n).

Instead of solving top-down with recursion, we solve bottom-up with a simple loop — and instead of an array, we use just two variables.

The key recurrence is:
$dp[i] = dp[i+1] \times \mathbb{1}[\text{s[i]} \neq \text{'0'}] + dp[i+2] \times \mathbb{1}[10 \leq \text{s[i..i+1]} \leq 26]$

Since dp[i] only depends on dp[i+1] and dp[i+2], we can use two variables — let's call them next1 (representing dp[i+1]) and next2 (representing dp[i+2]) — and iterate from right to left.

Think of it like climbing a staircase from the end of the string backward. At each step, you look at the one step ahead and two steps ahead to decide how many paths lead from here to the end. You only ever need to remember the two steps immediately ahead of you.

The base case is: standing at the end of the string (past all characters), there is exactly 1 way to decode — the empty decoding. So next1 = 1 initially.

This approach is:

• Iterative: No recursion, no stack overhead.
• O(1) space: Just two variables instead of an array.
• O(n) time: One pass through the string.

Let's trace with s = "226":

Step 1: Initialize: next1 = 1 (dp[3], past end), next2 = 0 (dp[4], out of range).

Step 2: i = 2, s[2] = '6' ≠ '0'.

• Single digit valid: current = next1 = 1
• Two digits: no index 3 exists → skip.
• current = 1. Update: next2 = next1 = 1, next1 = current = 1.

Step 3: i = 1, s[1] = '2' ≠ '0'.

• Single digit valid: current = next1 = 1
• Two digits: s[1..2] = "26", 26 ≤ 26 → valid: current += next2 = 1. current = 2.
• Update: next2 = next1 = 1, next1 = current = 2.

Step 4: i = 0, s[0] = '2' ≠ '0'.

• Single digit valid: current = next1 = 2
• Two digits: s[0..1] = "22", 22 ≤ 26 → valid: current += next2 = 1. current = 3.
• Update: next2 = next1 = 2, next1 = current = 3.

Step 5: Loop finished. Answer = next1 = 3.

We computed the same answer as before but using only O(1) extra space and no recursion.

1. If the string is empty or starts with '0', return 0
2. Initialize next1 = 1 (represents dp[n], base case) and next2 = 0 (represents dp[n+1])
3. Iterate from i = n-1 down to 0:
   • Set current = 0
   • If s[i] != '0': add next1 to current (single-digit decoding)
   • If i + 1 < n and s[i..i+1] forms a number between 10 and 26: add next2 to current (two-digit decoding)
   • Shift: next2 = next1, next1 = current
4. Return next1 (which now holds dp[0])

Time Complexity: O(n)

We iterate through the string exactly once from right to left. Each iteration does O(1) work — checking characters, computing a two-digit number, and updating two variables. Total: O(n).

Space Complexity: O(1)

We use only two integer variables (next1 and next2) regardless of the input size. No arrays, no recursion stack. This is the most space-efficient solution possible.