LeetCode 91 – Decode Ways

Decode Ways is Climbing Stairs with the steps made conditional, and that one change turns a five-line problem into one where most wrong answers come from a single character: '0'. The recurrence takes a minute. The zeros take the rest of the interview.

The problem

'A' through 'Z' map to "1" through "26". Given a string of digits, count the ways it can be decoded back into letters.

"12"    -> 2      "AB" (1 2)  or  "L" (12)
"226"   -> 3      "BZ" (2 26), "VF" (22 6), "BBF" (2 2 6)
"06"    -> 0      no letter is "06", and "0" is not a letter either
"0"     -> 0
"10"    -> 1      only "J" (10) -- 1 then 0 is not decodable
"100"   -> 0      10 then 0 -- dead end
"2101"  -> 1      "U A A" (21 01)? no. Only 2 10 1 = "BJA"
"27"    -> 1      27 is not a letter, so only 2 then 7

Work through "100" and "2101" by hand before writing anything. They are the two shapes that break naive solutions, and neither is in the examples LeetCode shows you.

The recurrence, before the zeros

Same question as Climbing Stairs: what was the last move? The final letter came from either one digit or two, so:

ways(i) = ways(i-1)   if the single digit s[i-1] is decodable
        + ways(i-2)   if the pair s[i-2..i-1] is decodable

Which is Fibonacci with each term gated by a validity test. If every digit and every pair were valid, "1111" would give 5 — and it does. The gates are the whole problem.

The two gates

single digit  s[i-1] != '0'                    "0" decodes to nothing
two digits    10 <= value(s[i-2..i-1]) <= 26   "01" is not 1, and 27+ is no letter

The lower bound on the pair is 10, not 1, and that is the subtle one. A leading zero makes a two-digit reading invalid outright — "01" is not a valid encoding of 'A', because 'A' is written "1". Testing value <= 26 without the lower bound accepts "06" and returns 1 instead of 0.

Notice that a '0' contributes nothing on its own and can only survive as the second half of 10 or 20. That single sentence explains every zero case in the examples: "100" is 10 followed by a 0 that has no partner, so it dies.

The base case that is easy to get wrong

ways(0) = 1     the empty string has exactly one decoding: the empty one
ways(1) = s[0] != '0' ? 1 : 0

ways(0) = 1 is not a convention pulled from nowhere — it has to be 1 for the two-digit branch to work. Decoding "12" as the single letter "L" adds ways(0) to the total, so a zero there would lose that decoding entirely.

Java

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;

        int twoBack = 1;                     // ways(0): the empty decoding
        int oneBack = 1;                     // ways(1): s[0] != '0', checked above

        for (int i = 2; i <= s.length(); i++) {
            int current = 0;

            if (s.charAt(i - 1) != '0') {
                current += oneBack;          // take one digit
            }

            int pair = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (pair >= 10 && pair <= 26) {
                current += twoBack;          // take two -- note the LOWER bound
            }

            twoBack = oneBack;
            oneBack = current;
        }

        return oneBack;
    }
}

current starts at 0 and both branches are additive, so a position where neither gate opens produces 0 and the zero propagates forward through every later term. That is the mechanism by which "100" returns 0 — no explicit dead-end detection is needed, the arithmetic does it.

Building pair from two charAt calls rather than Integer.parseInt(s.substring(i-2, i)) avoids allocating a string on every iteration of a loop that runs the length of the input.

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == "0":
            return 0

        two_back, one_back = 1, 1

        for i in range(2, len(s) + 1):
            current = 0

            if s[i - 1] != "0":
                current += one_back

            if 10 <= int(s[i - 2:i]) <= 26:      # the lower bound rejects "01".."09"
                current += two_back

            two_back, one_back = one_back, current

        return one_back

10 <= int(s[i-2:i]) <= 26 is the chained comparison stating both gates at once, and it is the clearest expression of the rule in either language. int("06") is 6, which is why the lower bound rather than the string is what does the rejecting.

Complexity

One pass, constant memory. If the interviewer asks for the decodings themselves rather than the count, the answer changes character completely: there can be exponentially many, so it becomes backtracking and the output dominates. Knowing that counting and enumerating are different problems is worth saying.

The pattern

Climbing Stairs (70) is this with both gates permanently open. Decode Ways II (639) adds a '*' wildcard matching 1–9, which multiplies the branch counts instead of adding 1 — the same recurrence with weights. Fibonacci is the degenerate case.

The transferable move is conditional Fibonacci: when a linear DP's transitions can be individually disabled, keep the two-variable shape and put the conditions on the additions rather than restructuring the loop.

What the interviewer is checking

• That you derive the recurrence from "what was the last letter?" and recognise Fibonacci.
• 10 <= pair <= 26 — the lower bound, not just the upper.
• That '0' only survives as the second digit of 10 or 20.
• "0", "06", "10", "100" and "2101".
• That ways(0) = 1, and why it must be.
• A leading zero rejected up front.
• That you compress to two variables rather than keeping the array.