Decode Ways

1. Problem & Core Objective

'A'–'Z' map to "1"–"26". Given a digit string, count how many ways it can be decoded.

s = "12"     →  2      "AB" (1 2) or "L" (12)
s = "226"    →  3      "BZ", "VF", "BBF"
s = "06"     →  0      no valid decoding — leading zero

Constraints: 1 <= s.length <= 100 · digits only

What's actually being tested: the Climbing Stairs recurrence with validity guards. The structure is dp[i] = dp[i−1] + dp[i−2], but each term is included only if the corresponding one- or two-digit piece is legal — and zero handling is where almost everyone fails.

2. First-Principles Thought Process

The same last-move reasoning

To decode a prefix of length i, the final letter came from either:

• the last one digit, if it's 1–9 — add dp[i−1]
• the last two digits, if they form 10–26 — add dp[i−2]

dp[i] = (oneDigitValid ? dp[i-1] : 0) + (twoDigitValid ? dp[i-2] : 0)

Identical shape to Climbing Stairs; the guards are the only addition.

The three zero rules

Zero is the entire difficulty, and it has three distinct consequences:

'0' alone is never a letter. There's no letter 0, so a single '0' contributes nothing — dp[i−1] is excluded whenever s[i−1] == '0'.

'0' must be preceded by 1 or 2. Only "10" and "20" are valid two-digit pieces ending in zero. So "30", "06", "00" are all undecodable.

A leading '0' kills everything. "06" has no decoding at all — the first character can't start any valid piece.

Why two-digit validity is a range, not just "two digits"

"27" is not a valid letter, so it must not contribute. The check is 10 <= value <= 26, and the lower bound matters as much as the upper: "07" is 7 numerically but has a leading zero, making it an invalid two-digit piece.

Checking only value <= 26 would wrongly accept "06" as the letter F.

Base cases

dp[0] = 1 — one way to decode the empty prefix (do nothing). This is the convention that makes the recurrence work at i = 2.

dp[1] = s[0] == '0' ? 0 : 1.

3. Solution Paths

Approach 1 — Recursion over split points

public int numDecodings(String s) {
    return decode(s, 0);
}

private int decode(String s, int i) {
    if (i == s.length()) return 1;                  // consumed everything — one valid decoding
    if (s.charAt(i) == '0') return 0;               // no piece can start with 0

    int ways = decode(s, i + 1);                    // take one digit
    if (i + 1 < s.length()) {
        int two = Integer.parseInt(s.substring(i, i + 2));
        if (two <= 26) ways += decode(s, i + 2);    // take two digits
    }
    return ways;
}

• Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Why does reaching the end return 1 rather than 0?"

Because consuming the whole string means one complete valid decoding has been formed. Returning 0 would make every path contribute nothing and the total would always be 0.

It's the same convention as dp[0] = 1 in the tabulated version: the empty string has exactly one decoding — the empty one.

⭐ "Why check s.charAt(i) == '0' at the top rather than inside the branches?"

Because no valid piece can begin with '0' — neither a one-digit letter nor a two-digit one. Rejecting at entry handles both in one place.

Note the two-digit check two <= 26 alone wouldn't catch it: "06" parses to 6, which passes <= 26, but "06" isn't a letter. The leading-zero rejection is what makes the <= 26 test sufficient afterwards.

"Why is this exponential?"

Two branches per position, so 2^n paths, while only n distinct suffixes exist. At n = 100 that's 10^30.

"Is substring plus parseInt a problem?"

It allocates and parses per call, which is wasteful. (s.charAt(i) - '0') * 10 + (s.charAt(i+1) - '0') is arithmetic only, and the tabulated version below uses that.

Approach 2 — Tabulation

public int numDecodings(String s) {
    int n = s.length();
    if (s.charAt(0) == '0') return 0;               // leading zero — nothing works

    int[] dp = new int[n + 1];
    dp[0] = 1;                                       // empty prefix: one decoding
    dp[1] = 1;                                       // first char is non-zero, checked above

    for (int i = 2; i <= n; i++) {
        if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];          // one-digit piece

        int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
        if (two >= 10 && two <= 26) dp[i] += dp[i - 2];           // two-digit piece
    }
    return dp[n];
}

Trace — s = "226":

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

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why two >= 10 as well as <= 26?"

Because a two-digit piece must genuinely have two digits. "06" computes to 6, which passes <= 26, but "06" is not a letter — it has a leading zero.

Without the lower bound, "06" would count as F and the answer for "06" would be 1 instead of 0.

The >= 10 test is exactly "the first of the two digits is non-zero", expressed arithmetically.

⭐ "Why dp[0] = 1?"

Convention: the empty prefix has exactly one decoding, the empty one. It's what makes dp[2] correct when the whole two-character string forms one letter — "26" should give 1 from the two-digit branch, which reads dp[0].

Setting dp[0] = 0 would make every two-digit-only decoding vanish.

⭐ "Why is the leading-zero check separate rather than folded into the loop?"

Because dp[1] needs it. The loop starts at i = 2, so it never examines s[0] as a standalone piece. Without the upfront check, dp[1] would be set to 1 for a string starting with '0', and everything downstream would be wrong.

I verified it: with the check omitted, "06" returns 1 and "0" returns 1, where both should be 0. The check is load-bearing, not defensive.

"Why index s.charAt(i-1) rather than s.charAt(i)?"

Because dp is 1-indexed over prefix lengths while the string is 0-indexed over positions. dp[i] concerns the prefix of length i, whose last character is at index i−1.

That offset is the most common source of bugs here, and it's why I'd trace i = 2 explicitly.

"Can dp[i] stay 0?"

Yes — when neither piece is valid, such as "30" at i = 2: '0' isn't a one-digit letter, and 30 > 26. Then dp[2] = 0, and since everything after reads it, the whole answer becomes 0. Correct, since "30" is undecodable.

Approach 3 — Rolling variables (optimal)

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

    int twoBack = 1, oneBack = 1;                   // dp[0], dp[1]

    for (int i = 2; i <= s.length(); i++) {
        int current = 0;
        if (s.charAt(i - 1) != '0') current += oneBack;

        int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
        if (two >= 10 && two <= 26) current += twoBack;

        twoBack = oneBack;
        oneBack = current;
    }
    return oneBack;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why does current start at 0 rather than being assigned?"

Because both branches are conditional — it's genuinely possible that neither applies, and the answer for that prefix is 0.

Starting from 0 and adding makes that natural. Assigning current = oneBack + twoBack and then subtracting would be both uglier and error-prone.

"Why is rolling valid here?"

Fixed two-cell window — dp[i] reads only dp[i−1] and dp[i−2]. Same test as everywhere in this section.

"Could the count overflow?"

Yes, and it's worth being concrete. "1" repeated 100 times admits both splits at every position, and the count is Fibonacci(101) = 573,147,844,013,817,084,101.

I computed that rather than estimating: it overflows int (max ≈ 2.1 × 10^9) by eleven orders of magnitude, and overflows long as well (max ≈ 9.2 × 10^18).

LeetCode's constraints promise the answer fits in int, but that's a guarantee about the test data, not about the input space — a legal input exists that no primitive can hold. Worth flagging rather than assuming.

Comparison

4. Why the Optimal Wins

The structure is Climbing Stairs; the content is the validity guards. The DP pipeline is mechanical once the recurrence is written, and the rolling step applies because the window is fixed.

What makes this question Medium rather than Easy is entirely zero handling — three separate rules, each of which silently changes the answer if missed.

The framing worth keeping:

dp[i] = dp[i−1] + dp[i−2], but each term is gated on its piece being legal. A one-digit piece needs a non-zero; a two-digit piece needs 10 <= value <= 26 — and the lower bound is what rejects "06".

5. Java Prerequisites

Two-digit value without allocating

int two = (s.charAt(i-2) - '0') * 10 + (s.charAt(i-1) - '0');

Cheaper than Integer.parseInt(s.substring(i-2, i)) and avoids the allocation.

The three zero rules

if (s.charAt(0) == '0') return 0;                  // leading zero kills everything
if (s.charAt(i-1) != '0') current += oneBack;      // a lone '0' is not a letter
if (two >= 10 && two <= 26) current += twoBack;    // >= 10 rejects "06"

Index offset — dp is over prefix lengths, the string over positions, so dp[i] looks at s.charAt(i-1).

dp[0] = 1 — the empty prefix has one decoding.

6. Interview Communication Guide

Clarifying questions: Can the string contain '0' (yes — and it's the whole difficulty)? Is "0" decodable (no, answer 0)? Are leading zeros in a two-digit piece allowed (no — "06" is invalid)? Could the answer exceed int (worth raising; "1" × 100 would)?

The pitch

"The structure is Climbing Stairs. To decode a prefix of length i, the last letter came from either the final one digit or the final two — so dp[i] = dp[i−1] + dp[i−2].

The difference is that each term is gated on validity. The one-digit piece counts only if that digit isn't '0', since there's no letter 0. The two-digit piece counts only if the pair is in 10..26.

The lower bound on that range is the part worth emphasising. '06' computes to 6, which passes <= 26, but it isn't a letter — it has a leading zero. >= 10 is exactly 'the first of the two digits is non-zero', and without it '06' returns 1 instead of 0.

There are three zero rules in total: a lone '0' is never a letter; a '0' must be preceded by 1 or 2; and a leading '0' makes the whole string undecodable. That last one needs a separate check before the loop, because the loop starts at i = 2 and never examines s[0] as a standalone piece.

dp[0] = 1 by convention — the empty prefix has one decoding — which is what makes a whole-string two-digit decoding like '26' come out as 1.

One index detail I'd trace explicitly: dp is indexed by prefix length while the string is indexed by position, so dp[i] looks at s.charAt(i-1). That offset is the usual source of bugs.

O(n) time, and since the window is fixed at two cells, two rolling variables give O(1) space.

One thing worth flagging: '1' × 100 admits both splits everywhere, giving Fibonacci(101), which is about 5.7 × 10^20. That overflows not just int but long. The constraints promise the answer fits in int, but that's a guarantee about the test data, not the input space."

Edge cases to volunteer:

Name "06" and "100". The first isolates the >= 10 bound; the second has a valid prefix "10" followed by an undecodable "0", so it checks that a mid-string zero propagates correctly to 0.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the string could contain '*' matching any digit 1–9?"

LeetCode 639. The recurrence is the same, but each branch multiplies by the number of digits the wildcard could be. '*' alone is 9 ways; "1*" is 9 (11–19); "2*" is 6 (21–26); "**" is 15. Considerably fiddlier, and the answer needs a modulus.

⭐ "Return the actual decodings, not the count."

Backtracking, not DP — there can be exponentially many. Counting and enumerating have genuinely different complexities, as in Climbing Stairs.

"What if the alphabet went up to 'ZZ' = 702?"

Pieces of up to three digits, so dp[i] reads three cells back. Still a fixed window, so three rolling variables. The validity range widens and the zero rules extend to three-digit prefixes.

"What if n were 10^5?"

The rolling version is O(n) and O(1), so it scales — but the count would overflow anything short of BigInteger. In practice such problems ask for the answer modulo 10^9 + 7, which keeps it in int.

"Count decodings that use at most k two-digit pieces."

A second dimension: dp[i][j] for j two-digit pieces used. O(n · k) time and space, and the rolling becomes a pair of rows rather than a pair of scalars.

"What if the mapping were arbitrary rather than 1–26?"

Pass the valid piece set as a parameter and replace the range test with a lookup. The recurrence is unchanged — which shows the structure was never about the specific numbers, only about maximum piece length.