91. Decode Ways

Decode Ways looks like Climbing Stairs wearing a disguise — same “reach here from one or two steps back” count — but the zeros are what make it a medium. Get the digit validity right and it’s a tidy one-pass 1D DP; get it wrong and a single "0" silently inflates your answer.

The problem

Letters A–Z map to "1"–"26", so a digit string can be split back into letters in more than one way. Given a string of digits, count how many valid decodings it has. (Full statement on LeetCode.)

Take "226": you can read it as 2 2 6 → BBF, 22 6 → VF, or 2 26 → BZ. Three ways. But "06" has zero ways — no letter is "06", and "0" alone maps to nothing.

Intuition: count like Climbing Stairs, but validate each cut

Let dp[i] be the number of ways to decode the first i characters. To land on position i, the last chunk you peeled off was either one digit or two:

• One digit s[i-1]: legal only when it isn’t '0' (there’s no letter for 0). If legal, it contributes dp[i-1] ways.
• Two digits s[i-2..i-1]: legal only when they form a number in $[10, 26]$. That range check quietly rejects "07" (below 10, a leading zero) and "27" (above 26). If legal, it contributes dp[i-2] ways.

Those two branches never overlap — the final chunk has a fixed length — so you add them:

$dp[i] = \underbrace{[\,s_{i-1}\neq 0\,]\cdot dp[i-1]}_{\text{take one}} + \underbrace{[\,10 \le s_{i-2}s_{i-1} \le 26\,]\cdot dp[i-2]}_{\text{take two}}$

That’s the Fibonacci skeleton from Climbing Stairs with two gates bolted on. The base case dp[0] = 1 (the empty prefix decodes exactly one way — as nothing) is what makes a valid two-digit opener like "12" count correctly.

Solution

Each dp[i] needs only the two values before it, so two rolling variables replace the array. I keep prev1 (ways up to the last char) and prev2 (ways up to the one before it):

class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;   // a leading zero decodes to nothing

        int prev2 = 1;              // dp[i-2]: empty prefix has one decoding
        int prev1 = 1;              // dp[i-1]: first char is valid (checked above)

        for (int i = 1; i < s.length(); i++) {
            int cur = 0;
            // single digit: valid unless it's '0'
            if (s.charAt(i) != '0') {
                cur += prev1;
            }
            // two digits s[i-1..i], valid when in 10..26
            int two = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
            if (two >= 10 && two <= 26) {
                cur += prev2;
            }
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

If a character is a '0' that can’t join a valid pair — say the 0 in "100" — both gates fail, cur stays 0, and that zero propagates forward to a final answer of 0. That’s the correctness you want, not a crash.

Complexity

	Time	Space
Rolling DP	$O(n)$	$O(1)$

One left-to-right pass, two integers of state. A full dp[] array is equally fast but spends $O(n)$ space you never read more than two cells back into.

In an interview

Say the mapping to Climbing Stairs out loud first — “it’s the same count from one or two positions back” — then immediately flag what makes it harder: the zeros. That framing shows you spotted the pattern and its complication. Walk through "0", "06", and "10" on the board before you write, because the zero handling is exactly where this problem is graded. The classic bug is treating any two-digit slice as valid; "27" and "70" must both be rejected, which is why the check is the full $[10, 26]$ range and not just “starts with 1 or 2.”

The counting-over-partitions idea carries straight into Word Break, which asks the same “can I chop this string into valid pieces?” question with a dictionary instead of a number range. The rolling-state trick is the 1D DP pattern itself.

References

• LeetCode 91 — Decode Ways