Decode Ways (LC 91)

Pattern: Dynamic Programming (string parsing)
Difficulty: Medium
Key Concept: Ways to decode a prefix equal ways after one valid digit plus ways after one valid two-digit letter, with careful handling of '0'.

Problem Statement

A message containing letters A-Z is encoded to digits using:

• 'A' → "1" … 'Z' → "26".

Given a string s containing only digits, return the number of ways to decode it.

Input: s (non-empty string of digits).
Output: int count.

Examples:

• "12" → 2 ("AB" or "L").
• "226" → 3.
• "06" → 0 (leading zero invalid).

---

1. Algorithm & Pseudocode

Brute force

1. From index i, try taking one digit if not '0'; try two digits if value 10–26.
2. Recurse to remainder; sum counts.
3. Without memo: exponential.

Pseudocode:

function ways(i):
    if i == n: return 1
    if s[i] == '0': return 0
    ans = ways(i + 1)
    if i + 1 < n and int(s[i..i+2]) in [10..26]:
        ans += ways(i + 2)
    return ans

Optimal

1. dp[i] = ways to decode s[i..n); often easier: dp[i] for prefix ending at i.
2. Forward: dp[0]=1 if s[0]!='0'. For each i, update based on one-digit and two-digit moves.
3. Classic: dp[i] = number of ways for first i characters (dp[0]=1), iterate i from 1 to n.

Pseudocode (prefix dp):

dp[0] = 1
for i from 1 to n:
    dp[i] = 0
    if s[i-1] != '0': dp[i] += dp[i-1]
    if i >= 2 and 10 <= int(s[i-2:i]) <= 26: dp[i] += dp[i-2]
return dp[n]

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why '0' breaks single-digit: No letter maps to 0 alone; '0' must pair with previous digit as 10 or 20 (when valid).

Why two-digit check is 10–26: 01 is not a valid two-letter code; 27 is out of alphabet.

Why DP: Overlapping suffixes/prefixes—same index i reached many times in recursion.

---

3. The Dry Run

s = "226", n = 3. dp[i] = ways for first i chars.

i	one-digit (s[i-1])	two-digit s[i-2:i]	dp[i]
0	—	—	1 (empty)
1	‘2’ ok → +dp[0]=1	—	1
2	‘2’ ok → +dp[1]=1	“22” ok → +dp[0]=1	2
3	‘6’ ok → +dp[2]=2	“26” ok → +dp[1]=1	3

---

4. Java Solution

Brute Force

public class Solution {
    public int numDecodings(String s) {
        return dfs(s, 0);
    }

    private int dfs(String s, int i) {
        if (i == s.length()) {
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        int ans = dfs(s, i + 1);
        if (i + 1 < s.length()) {
            int two = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
            if (two >= 10 && two <= 26) {
                ans += dfs(s, i + 2);
            }
        }
        return ans;
    }
}

Time: Exponential without memo. Space: O(n) stack.

Optimal

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;

        for (int i = 2; i <= n; i++) {
            int one = s.charAt(i - 1) - '0';
            if (one >= 1 && one <= 9) {
                dp[i] += dp[i - 1];
            }
            int two = (s.charAt(i - 2) - '0') * 10 + one;
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

Time: O(n). Space: O(n); can compress to O(1) with prev2, prev1.

---

5. The “Java vs. Others” Edge

• Char arithmetic c - '0' avoids Integer.parseInt on substrings in the hot loop.
• dp[1] initialization handles "0" early (only one char).
• For O(1) space, mirror House Robber rolling variables: cur depends on prev1 and prev2.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute DFS	O(2^n) worst	O(n)	Fibonacci-like branching
DP (array)	O(n)	O(n)	Clear for interviews
DP (rolling)	O(n)	O(1)	Same recurrence