Decode Ways LeetCode 91 Deep Dive

LeetCode 91 Decode Ways gives you a string of digits and asks how many ways you can decode it back into letters, where A=1, B=2, …, Z=26. Every character maps to a letter, so you must partition the string into valid one- or two-digit chunks that all fall in the 1–26 range.

The classic example is "226": you can read it as B+Z (2,26), V+F (22,6), or B+B+F (2,2,6) — three total ways. The challenge is that the number of valid decodings can grow exponentially, so brute-force enumeration is far too slow. You need DP to count efficiently.

Zeros make this deceptively tricky. The digit 0 has no direct letter mapping, so a standalone 0 immediately kills that decode path. It can only appear as the second digit of 10 or 20. Handling zeros correctly is where most implementations break.

Once you strip away the letter-mapping theme, Decode Ways is structurally identical to Climbing Stairs — except some steps are blocked. In Climbing Stairs you can take 1 or 2 steps at any time. In Decode Ways you can "take" a single digit (1 step) if it is not zero, or a two-digit chunk (2 steps) if the number it forms is between 10 and 26.

The recurrence is dp[i] += dp[i-1] if the single-digit decode is valid, and dp[i] += dp[i-2] if the two-digit decode is valid. If neither is valid — for example at a standalone zero — dp[i] remains 0, which propagates and eventually zeroes out the count for all future positions that depend on this one.

This Fibonacci structure means dp[i] depends only on dp[i-1] and dp[i-2], just like the Fibonacci sequence. That makes O(1) space optimization straightforward: you only need two variables instead of the full array.

Define dp[i] as the number of ways to decode the first i characters of the string. The base cases are dp[0] = 1 (empty string has exactly one decode — do nothing) and dp[1] = 1 if s[0] != "0" else 0.

For each position i from 2 to n, first set dp[i] = 0. Then check two conditions independently: if s[i-1] != "0", the single digit at position i is valid, so add dp[i-1]. If the two-digit number formed by s[i-2..i-1] is between 10 and 26 inclusive, add dp[i-2].

Running through "226": dp[0]=1, dp[1]=1 (s[0]="2" != "0"). At i=2: single "2" valid → dp[2] += dp[1] = 1; two-digit "22" in [10,26] → dp[2] += dp[0] = 1; dp[2] = 2. At i=3: single "6" valid → dp[3] += dp[2] = 2; two-digit "26" in [10,26] → dp[3] += dp[1] = 1; dp[3] = 3. Answer: 3.

Most incorrect Decode Ways solutions fail because of zero handling. The digit "0" cannot be decoded on its own — there is no letter for 0. It must be the second digit of either "10" (J) or "20" (T). Any other two-digit combination ending in 0, like "30", "40", or "00", is also invalid.

When dp[i] stays 0 because the current character is a standalone zero, that zero propagates forward and eventually makes the total count 0. For example, "30" has 0 decodings: "3" and "0" cannot be split into a valid single digit, and "30" exceeds 26 so it is not a valid two-digit code either.

Leading zeros like "06" are also a trap: you cannot treat it as the number 6 (because "0" alone is invalid for single-digit decode) and you cannot use "06" as a two-digit code (06 = 6, but 06 as a string would require treating the leading zero as valid, which it is not — the valid range check uses the integer value, and only 10–26 are legal).

Because dp[i] depends only on dp[i-1] and dp[i-2], you do not need to store the entire DP array. Replace dp[i-1] with a variable prev1 and dp[i-2] with prev2. After computing each new value, shift: prev2 becomes prev1, prev1 becomes the new value.

This is the same optimization used in House Robber and Fibonacci. Initialize prev2 = 1 (represents dp[0]) and prev1 = 1 if s[0] != "0" else 0 (represents dp[1]). Then iterate from index 2 to n, computing curr = 0, adding prev1 if single digit valid, adding prev2 if two digits valid, then setting prev2 = prev1 and prev1 = curr.

The result is an O(n) time, O(1) space solution — a meaningful improvement over the O(n) space DP array, especially for very long strings. This is almost always the expected final solution in an interview setting.

The Python implementation uses two variables and a single loop. Check s[i-1] != "0" for the single-digit branch, and check 10 <= int(s[i-2:i]) <= 26 for the two-digit branch. The integer conversion handles leading zeros automatically because "06" converts to 6, which is outside [10,26], correctly returning 0 ways.

The Java implementation mirrors the Python logic with explicit character arithmetic. Use Character.getNumericValue(s.charAt(i-1)) for the single digit and (s.charAt(i-2) - "0") * 10 + (s.charAt(i-1) - "0") for the two-digit number. Avoid Integer.parseInt on substrings in tight loops as it has overhead; the arithmetic approach is cleaner.

Both implementations run in O(n) time and O(1) space. Edge cases to test: empty string (return 0 or 1 depending on problem spec), "0" (return 0), "10" (return 1), "100" (return 0), "110" (return 1), "226" (return 3), "2611055971756562" (stress test).

Decode Ways belongs to the linear DP family where you scan the string left to right and build the answer from subproblems. The closest relative is Decode Ways II (LeetCode 639), which adds the wildcard "*" that can represent any digit 1–9. The "*" multiplies the number of valid decodings dramatically and requires careful case analysis on top of the base recurrence.

Climbing Stairs (LeetCode 70) and House Robber (LeetCode 198) share the same two-variable rolling pattern. Climbing Stairs is the pure Fibonacci without validity constraints. House Robber has the constraint that you cannot take adjacent houses — analogous to how Decode Ways cannot use a "0" as a standalone step.

If you can solve Decode Ways cleanly in an interview — handling zeros, the base cases, and the space optimization — you have demonstrated mastery of the core linear DP pattern. Practice with YeetCode flashcards to internalize the recurrence: "single digit valid if not zero; two digits valid if 10–26; otherwise dead end."