105.Decode Ways

MediumBlind 751-D Dynamic Programming · 7/12

Problem

A message of letters was encoded with 'A' → "1", 'B' → "2", ..., 'Z' → "26". Given the digit string s, return the number of ways to decode it back into letters.

A valid split uses only the codes "1"–"26". A code can't have a leading zero, so "06" is invalid, and a lone "0" maps to nothing. If the string cannot be decoded at all, return 0.

Examples

Input:  s = "12"
Output: 2
Explanation: "AB" (1 2) or "L" (12).

Input:  s = "226"
Output: 3
Explanation: "BZ" (2 26), "VF" (22 6), "BBF" (2 2 6).

Input:  s = "06"
Output: 0
Explanation: "06" is not a valid code and "0" alone decodes to nothing.

Constraints

1 <= s.length <= 100
s contains only digits and may contain leading zeros.
The answer fits in a 32-bit integer.

💡 Key Insight

Let f(i) be the number of ways to decode the suffix s[i..]. The first code starting at i is either one digit (valid if s[i] != '0') or two digits (valid if s[i..i+1] is between 10 and 26), so f(i) = (s[i] != '0' ? f(i + 1) : 0) + (10 <= s[i..i+1] <= 26 ? f(i + 2) : 0), with f(n) = 1 (the empty suffix has one decoding: stop). It is Climbing Stairs with conditions on each step, so it also reduces to two rolling variables.

Recursion (Brute Force)

TimeO(2ⁿ)SpaceO(n)

Intuition

At position i, try to peel off a one-digit code and a two-digit code, recursing on what's left. Every branch that reaches the end of the string is one full decoding.

Recurrence: f(i) = [s[i] != '0'] · f(i + 1) + [10 <= int(s[i..i+1]) <= 26] · f(i + 2), f(n) = 1.

Algorithm

dfs(i): if i == n return 1; if s[i] == '0' return 0 (no code starts with 0).
ways = dfs(i + 1).
If i + 1 < n and s[i..i+1] is 10–26, add dfs(i + 2).
Return ways; answer dfs(0).

Visualization

s = "2226". f(2) and f(3) are each computed more than once.

flowchart TD
    A["f(0) '2226'"] -->|"take 2"| B["f(1) '226'"]
    A -->|"take 22"| C["f(2) '26'"]
    B -->|"take 2"| D["f(2) '26'"]
    B -->|"take 22"| E["f(3) '6'"]
    C -->|"take 2"| F["f(3) '6'"]
    C -->|"take 26"| G["f(4) = 1"]
    D -->|"take 2"| H["f(3) '6'"]
    D -->|"take 26"| I["f(4) = 1"]
    E -->|"take 6"| J["f(4) = 1"]

f(3) = 1, f(2) = 2, f(1) = f(2) + f(3) = 3, f(0) = f(1) + f(2) = 5.

Code

java

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

    // number of ways to decode s[i..]
    private int dfs(String s, int i) {
        if (i == s.length()) {
            return 1; // reached the end: one complete decoding
        }
        if (s.charAt(i) == '0') {
            return 0; // no code starts with '0'
        }
        int ways = dfs(s, i + 1); // single-digit code 1..9
        if (i + 1 < s.length()) {
            int two = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
            if (two <= 26) { // already >= 10 because s[i] != '0'
                ways += dfs(s, i + 2);
            }
        }
        return ways;
    }
}

Complexity

Time: O(2ⁿ) — up to two branches per position.
Space: O(n) — recursion depth.

Top-Down Memoization

TimeO(n)SpaceO(n)

Intuition

The number of decodings of a suffix doesn't depend on how we got there. Cache f(i) and each suffix is solved once.

Algorithm

memo of size n, filled with -1 (0 is a real answer).
Same recursion as above, but check/store memo[i].

Dry Run

s = "226"
dfs(2) '6'   = dfs(3) = 1                → memo[2] = 1
dfs(1) '26'  = dfs(2) + dfs(3) = 1 + 1   → memo[1] = 2
dfs(0) '226' = dfs(1) + dfs(2) = 2 + 1   → 3   (dfs(2) is a cache hit)

Code

java

import java.util.Arrays;

class Solution {
    private int[] memo;

    public int numDecodings(String s) {
        memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return dfs(s, 0);
    }

    private int dfs(String s, int i) {
        if (i == s.length()) {
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        int ways = dfs(s, i + 1);
        if (i + 1 < s.length()) {
            int two = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
            if (two <= 26) {
                ways += dfs(s, i + 2);
            }
        }
        memo[i] = ways;
        return ways;
    }
}

Complexity

Time: O(n) — n states, O(1) each.
Space: O(n) — memo and recursion stack.

Bottom-Up Tabulation

TimeO(n).SpaceO(n).

Intuition

Fill dp[i] (ways to decode s[i..]) from right to left; dp[i] reads dp[i + 1] and dp[i + 2], which are already filled.

Algorithm

dp of size n + 1; dp[n] = 1.
For i = n-1 .. 0:
- If s[i] == '0': dp[i] = 0.
- Else dp[i] = dp[i + 1], plus dp[i + 2] if i + 1 < n and s[i..i+1] <= 26.
Return dp[0].

Dry Run

s = "2101":

i	0 '2'	1 '1'	2 '0'	3 '1'	4 (end)
dp[i]	1	1	0	1	1

dp[3] = dp[4] = 1.
dp[2] = 0 (starts with 0).
dp[1] = dp[2] + dp[3] ("10" valid) = 0 + 1 = 1.
dp[0] = dp[1] ("21" valid, add dp[2] = 0) = 1. Only decoding: 2 10 1 → "BJA".

Code

java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[n] = 1; // empty suffix
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                dp[i] = 0;
                continue;
            }
            dp[i] = dp[i + 1];
            if (i + 1 < n && (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0') <= 26) {
                dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }
}

Complexity

Time: O(n).
Space: O(n).

Space-Optimized DPOptimal

TimeO(n)SpaceO(1)

Intuition

dp[i] only needs dp[i + 1] and dp[i + 2]. Keep them as next1 and next2 and slide leftwards.

Algorithm

next1 = 1 (dp[n]), next2 = 0 (dp[n + 1], never used validly).
For i = n-1 .. 0:
- curr = 0 if s[i] == '0'; else curr = next1 plus next2 if the two-digit code is ≤ 26.
- next2 = next1, next1 = curr.
Return next1.

Dry Run

flowchart LR
    A["s = '226'<br/>next1=1, next2=0"] -->|"i=2 '6'"| B["curr = 1<br/>next1=1, next2=1"]
    B -->|"i=1 '26' ok"| C["curr = 1 + 1 = 2<br/>next1=2, next2=1"]
    C -->|"i=0 '22' ok"| D["curr = 2 + 1 = 3<br/>next1=3, next2=2"]
    D --> E["return 3"]

Code

java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int next1 = 1; // dp[i + 1]
        int next2 = 0; // dp[i + 2]
        for (int i = n - 1; i >= 0; i--) {
            int curr = 0;
            if (s.charAt(i) != '0') {
                curr = next1; // one-digit code
                if (i + 1 < n && (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0') <= 26) {
                    curr += next2; // two-digit code 10..26
                }
            }
            next2 = next1;
            next1 = curr;
        }
        return next1;
    }
}

Complexity

Time: O(n) — one pass.
Space: O(1) — two integers.

Complexity Comparison

Approach	Time	Space
Recursion (Brute Force)	O(2ⁿ)	O(n)
Top-Down Memoization	O(n)	O(n)
Bottom-Up Tabulation	O(n)	O(n)
Space-Optimized DP	O(n)	O(1)

Common Pitfalls

Treating "0" as a valid single-digit code — it decodes to nothing, so dp[i] = 0 when s[i] == '0'.
Accepting two-digit codes like "05" or "27": the pair must be in 10..26.
Setting the base case dp[n] = 0 — the empty suffix contributes exactly one way.
Using 0 as the memo sentinel — many suffixes genuinely have 0 decodings, so a 0 sentinel re-explores them.
Strings like "100" and "30" have answer 0; make sure your code returns it instead of crashing.