4.23.7 — Decode Ways

LeetCode 91 · Medium · ★ Blind 75

The problem

A is 1, B is 2, up to Z which is 26. Given a string of digits, how many ways can it be decoded?

"12"    →  2     ("AB" = 1,2   or  "L" = 12)
"226"   →  3     ("BZ", "VF", "BBF")
"06"    →  0     (no letter is 0, and "06" is not a valid 6)

The pattern

Same shape as 4.23.1 Climbing Stairs — at each position you consume one digit or two — but now each move has a condition.

Let dp[i] be the number of ways to decode the first i characters.

dp[i] = \underbrace{dp[i-1] \ \text{if the last digit is 1–9}}_{\text{take one digit}} \ + \ \underbrace{dp[i-2] \ \text{if the last two form 10–26}}_{\text{take two digits}}

Counting, so the operator is +.

The three rules that decide everything

The whole problem is the validity conditions, and each has an input designed to catch you.

A single digit is valid unless it is 0. There is no letter 0, so "0" alone decodes zero ways.

A pair is valid only between 10 and 26. That means the first digit must be 1 or 2, and if it is 2 the second must be at most 6.

A leading zero in a pair is invalid. "06" is not 6 — the pair must start with 1 or 2, so 0 never begins a valid two-digit code. This is the case that breaks naive solutions, and "06" is on the test set for exactly that reason.

The consequence worth stating: a 0 in the input can only ever be decoded as part of 10 or 20. Any other 0 makes the whole string undecodable, and the count collapses to zero and stays there.

The solution

Python

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

        two_back, one_back = 1, 1            # dp[0] = 1 (empty), dp[1] = 1

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

            if s[i] != '0':                  # take one digit
                current += one_back

            two_digit = int(s[i - 1: i + 1])
            if 10 <= two_digit <= 26:        # take two digits
                current += two_back

            two_back, one_back = one_back, current

        return one_back

TypeScript

function numDecodings(s: string): number {
  if (!s || s[0] === '0') return 0;

  let twoBack = 1, oneBack = 1;

  for (let i = 1; i < s.length; i++) {
    let current = 0;

    if (s[i] !== '0') current += oneBack;

    const twoDigit = Number(s.slice(i - 1, i + 1));
    if (twoDigit >= 10 && twoDigit <= 26) current += twoBack;

    twoBack = oneBack;
    oneBack = current;
  }

  return oneBack;
}

dp[0] = 1 is the base case that trips people up. The empty string has exactly one decoding — the empty one. It looks like it should be 0, but making it 1 is what allows a valid two-digit code at the very start to be counted: for "12", the pair 12 contributes dp[0] = 1, which is correct.

The s[0] == '0' guard rejects a string that cannot start at all.

current starts at 0 every iteration, so a position where neither move is legal correctly yields 0 — and from then on every later position sees a 0 and stays 0. The zero propagates by itself, which is exactly right.

10 <= two_digit <= 26 covers the leading-zero rule for free, because "06" is 6, which is below 10.

Trace

"226"

i	char	one-digit?	two-digit	valid pair?	current
start					two_back = 1, one_back = 1
1	2	yes → +1	22	yes → +1	2
2	6	yes → +2	26	yes → +1	3

Answer 3 ✓ — "BBF", "VF", "BZ".

Now "06": the guard fires on s[0] == '0' and returns 0 immediately.

And "106": at i = 1 the char is 0, so no one-digit move; the pair 10 is valid, so current = dp[0] = 1. At i = 2 the char is 6, so current = dp[1] = 1; the pair 06 is invalid. Answer 1 — "JF" ✓.

Complexity

O(n) time, O(1) space.

Where this goes next

• Decode Ways II — the input may contain *, meaning any digit from 1 to 9. The same recurrence with counted possibilities instead of yes-or-no, and the arithmetic becomes fiddly. A good demonstration that the shape survives while the conditions get harder.
• Climbing Stairs — this recurrence with no conditions at all. 4.23.1.
• Word Break — the same "can I split this string" idea, but the pieces can be any length and are checked against a dictionary. 4.23.10.

The family: split a string into valid pieces. Fixed piece lengths give this problem; arbitrary lengths give Word Break; palindromic pieces give Palindrome Partitioning. Same skeleton, different validity test.

What the interviewer will push on

"Why is dp[0] = 1?" The empty string has one decoding, and that base value is what lets a leading two-digit code be counted.

"What does '06' do?" Zero ways. The pair rule requires 10 to 26, so a leading zero can never form a valid pair.

"Where can a 0 legally appear?" Only as the second digit of 10 or 20.

"Walk through '2101'." A good test — the answer is 1, and it exercises both zero rules.

"O(1) space?" Two variables, since only the previous two values are read.

One thing to volunteer: enumerate the three validity rules before writing code, and name the input that breaks each. This problem is not hard once the rules are written down; it is hard when you discover them one failing test at a time.

Next: 4.23.8 Coin Change — the classic optimisation DP, and the clearest proof that greedy fails.