AlgoMaster Logo

Decode Ways

Last Updated: March 28, 2026

medium
5 min read

Understanding the Problem

At each position in the string, we have a choice: take the current digit as a single character (if it's between 1 and 9), or take the current digit together with the next digit as a two-character group (if the pair forms a number between 10 and 26). The total number of decodings is the sum of all valid ways to make these choices across the entire string.

The tricky part is handling zeros. A '0' cannot stand alone, it can only be part of a two-digit group like "10" or "20". If a '0' appears in a position where it can't form a valid two-digit group (like after a '3' or another '0'), the entire decoding becomes impossible up to that point.

This structure, where the answer at each position depends on previous positions, is a textbook signal for dynamic programming. Each position's decode count depends on whether we take one digit or two, which connects it directly to the results at the previous one or two positions.

Key Constraints:

  • 1 <= s.length <= 100 -> With n up to 100, any polynomial approach works. But the recursive structure naturally leads to O(n).
  • s contains only digits -> No need to validate characters, but we do need to handle the digit '0' carefully since it has special decoding rules.
  • may contain leading zeros -> A string like "06" is valid input but has zero decodings. This is a key edge case.

Approach 1: Recursion (Brute Force)

Intuition

The most natural way to think about this problem is to make decisions from left to right. Standing at position i in the string, we ask: can I take one digit? Can I take two digits? If either option is valid, we recurse on the remaining substring and add up the results.

The base case is reaching the end of the string, which counts as one valid decoding (we successfully decoded everything). If we hit a '0', that branch dies because zero can't map to any letter on its own.

Algorithm

  1. Start from index 0.
  2. If we've reached the end of the string, return 1 (found a valid decoding).
  3. If the current character is '0', return 0 (invalid path).
  4. Count the ways by recursing on index + 1 (take one digit).
  5. If there's a next character and the two-digit number formed is between 10 and 26, also add the ways from recursing on index + 2.
  6. Return the total count.

Example Walkthrough

Input:

0
2
1
2
2
6
s

The recursion explores all branching paths. From index 0, we can take '2' (recurse on "26") or '22' (recurse on "6"). From "26", we can take '2' then '6', or take '26' directly. This gives us three paths: (2,2,6), (2,26), (22,6).

3
result

Code

We're recomputing the same suffixes over and over. What if we cached the result of each decode(i) the first time we compute it?

Approach 2: Recursion with Memoization (Top-Down DP)

Intuition

The brute force recursion has overlapping subproblems. If you draw out the recursion tree for a string like "1234", you'll see that decode(2) gets computed more than once. This is the classic signal for memoization.

The fix is simple: before computing decode(i), check if we've already computed it. If yes, return the cached result. If no, compute it, cache it, and return it. This turns our exponential solution into a linear one because each index is computed at most once.

Algorithm

  1. Create a memo array of size n, initialized to -1.
  2. Start from index 0 and follow the same recursive logic as Approach 1.
  3. Before computing decode(i), check if memo[i] is already set. If so, return it.
  4. After computing decode(i), store the result in memo[i].

Example Walkthrough

1Initialize memo array, start decode(0)
0
-1
decode(0)
1
-1
2
-1
1/6

Code

The memoized approach eliminates redundant computation, but still uses O(n) space for the memo array plus recursion stack. What if we iterated left to right and built the answer in a simple array?

Approach 3: Bottom-Up Dynamic Programming

Intuition

Instead of thinking recursively, we can build up the answer iteratively. Define dp[i] as the number of ways to decode the first i characters. The recurrence is:

  • If s[i-1] is not '0', then we can take it as a single digit: dp[i] += dp[i-1].
  • If the two-digit number formed by s[i-2] and s[i-1] is between 10 and 26, we can take them together: dp[i] += dp[i-2].

The base case is dp[0] = 1 (empty string has one way to decode: do nothing). If you've seen the Climbing Stairs problem, this will feel familiar. It's the same Fibonacci-like recurrence, but with validity checks on each "step."

Algorithm

  1. Create an array dp of size n + 1, initialized to 0.
  2. Set dp[0] = 1 (base case: one way to decode an empty prefix).
  3. Set dp[1] = 1 if s[0] is not '0', else dp[1] = 0.
  4. For each position i from 2 to n:
    • If s[i-1] is not '0', add dp[i-1] to dp[i] (single digit decode).
    • Parse the two-digit number from s[i-2] and s[i-1]. If it's between 10 and 26, add dp[i-2] to dp[i].
  5. Return dp[n].

Example Walkthrough

1Base case: dp[0]=1 (empty prefix has one decoding)
0
1
base
1
0
2
0
3
0
1/5

Code

We're storing the entire DP array, but at any position we only look at the previous two values. Can we use just two rolling variables instead?

Approach 4: Space-Optimized DP

Intuition

Since dp[i] depends only on dp[i-1] and dp[i-2], we don't need the full array. Two variables are enough. This is the same optimization that turns the Fibonacci array into two rolling variables.

We keep prev1 (representing dp[i-1]) and prev2 (representing dp[i-2]), update them as we iterate, and the final value of prev1 is our answer.

Algorithm

  1. Set prev2 = 1 (represents dp[0]) and prev1 = 1 if s[0] is not '0', else prev1 = 0 (represents dp[1]).
  2. For each position i from 2 to n:
    • Initialize current = 0.
    • If s[i-1] is not '0', add prev1 to current.
    • If the two-digit number from s[i-2..i-1] is between 10 and 26, add prev2 to current.
    • Shift: prev2 = prev1, prev1 = current.
  3. Return prev1.

Example Walkthrough

1Input string s = "11106"
0
1
1
1
2
1
3
0
4
6
1/6

Code