Blind 75 Visualized

#55 · 1D DP

Decode Ways

A message of digits encodes letters with A=1 … Z=26. Given a string of digits, return the number of ways to decode it. A zero cannot stand alone.

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Suffix DP table

dp[i] = the number of ways to decode the digits from position i to the end. A digit that is not zero can be a letter by itself (continue at i + 1); two digits forming 10 … 26 can be a letter together (continue at i + 2).

Memory layout

A flat array of n + 1 integers; dp[n] = 1 is the empty decoding. Only dp[i + 1] and dp[i + 2] are read.

OperationCost
timeO(n)
spaceO(n) table, O(1) with two variables

Validity rules for digits

A single digit is valid if it is 1 … 9. A pair is valid if it is 10 … 26, which for digits d1 d2 means d1 = 1 (any d2) or d1 = 2 and d2 ≤ 6. Zero is valid only as the second digit of 10 or 20.

Memory layout

No storage: two character comparisons.

OperationCost
per positionO(1)

Why it fits

  • Whatever the first letter is, the rest of the message is a smaller instance of the same problem, so the count is a sum of counts for shorter suffixes.
  • There are only n + 1 distinct suffixes, so counting each once makes the algorithm linear instead of exponential.
  • Each count needs only the next two, so the table can shrink to two numbers.

Why alternatives degrade

Greedy: always take two digits when possible:
It can miss valid splits: "226" decodes as 2-2-6, 22-6 and 2-26; taking 22 first discards the others.
Counting via combinatorics only:
Zeros and values above 26 make the number of valid splits depend on the local digits in a way a simple formula does not capture.
Plain recursion:
It re-decodes the same suffixes many times: exponential (like the Fibonacci recursion).

Four approaches, from naive to production

1 · beginner

Plain recursion

time O(2ⁿ)space O(n)

ways(i) decodes from position i: 0 for a leading zero, 1 at the end, otherwise ways(i + 1) plus ways(i + 2) when the next two digits form 10 … 26.

int numDecodings(string s) {
    function<int(int)> ways = [&](int i) -> int {
        if (i == (int)s.size()) return 1;
        if (s[i] == '0') return 0;
        int total = ways(i + 1);
        if (i + 1 < (int)s.size() && stoi(s.substr(i, 2)) <= 26) total += ways(i + 2);
        return total;
    };
    return ways(0);
}

Flaws & bottlenecks

  • The same suffix is decoded from several earlier choices.
  • The number of calls can grow like the Fibonacci numbers.
  • Converting two digits to a number allocates a slice each time.

Interviewer cross-questions

Why does a zero return 0?

Say: No letter is written with a leading zero, and a zero can only appear as the second digit of 10 or 20, which the previous step already consumed as a pair.

Why is it exponential?

Say: For strings like "111111", every position can be taken alone or paired, so the calls branch twice per position and sub-problems repeat.

How do you fix it?

Say: Cache each ways(i) (memoisation) or fill the answers from the end of the string.

2 · intermediate

Memoised recursion

time O(n)space O(n)

The same recursion, but each position's answer is stored so it is computed once. The two-digit test compares characters instead of converting to a number.

int numDecodings(string s) {
    unordered_map<int, int> memo;
    function<int(int)> ways = [&](int i) -> int {
        if (i == (int)s.size()) return 1;
        if (s[i] == '0') return 0;
        auto known = memo.find(i);
        if (known != memo.end()) return known->second;
        int total = ways(i + 1);
        if (i + 1 < (int)s.size() && (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6'))) total += ways(i + 2);
        memo[i] = total;
        return total;
    };
    return ways(0);
}

Flaws & bottlenecks

  • Still recursive: depth up to n.
  • Hash-table overhead for a dense integer range.
  • Two nested conditions on the pair are easy to mis-order.

Interviewer cross-questions

Why compare characters instead of parsing a number?

Say: It avoids creating a substring and a number for every position. "1" followed by anything, or "2" followed by 0 … 6, covers exactly 10 … 26.

What does the memo change?

Say: Each position is solved once, so the total number of recursive calls is at most about 2n.

Could the memo hold the zero case too?

Say: It could, but returning 0 immediately is cheaper than a lookup.

3 · advanced

Bottom-up table

time O(n)space O(n)

Fill dp from the last digit backwards: dp[n] = 1; for each non-zero digit dp[i] = dp[i + 1], plus dp[i + 2] if the next two digits form 10 … 26. Answer dp[0].

int numDecodings(string s) {
    int n = s.size();
    vector<int> dp(n + 1, 0);
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '0') continue;
        dp[i] = dp[i + 1];
        if (i + 1 < n && (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6'))) dp[i] += dp[i + 2];
    }
    return dp[0];
}

Flaws & bottlenecks

  • O(n) memory for values used only two steps later.
  • The `continue` for zero leaves dp[i] at 0, which depends on the array having been zero-filled.
  • A string that starts with "0" returns 0 (correct) but only after scanning everything.

Interviewer cross-questions

Why does dp[n] = 1?

Say: It represents the empty decoding. Every complete decoding ends by reaching position n, and each adds exactly one to the count.

What if the string is empty?

Say: The problem guarantees at least one character. For an empty string this code would return dp[0] = 1, which is the number of ways to decode nothing.

Can leading zeros inside the string zero out the whole answer?

Say: Yes: a "00" or a "30" cannot be decoded, so the suffix count becomes 0, and any prefix that must pass through it also gets 0.

4 · expert

Two rolling variables

time O(n)space O(1)

Keep only dp[i + 1] (next1) and dp[i + 2] (next2). For each digit compute cur from them and shift. O(1) extra memory, one pass.

int numDecodings(string s) {
    int next1 = 1, next2 = 0;
    for (int i = (int)s.size() - 1; i >= 0; i--) {
        int cur = 0;
        if (s[i] != '0') {
            cur = next1;
            if (i + 1 < (int)s.size() && (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6'))) cur += next2;
        }
        next2 = next1;
        next1 = cur;
    }
    return next1;
}

Flaws & bottlenecks

  • The values for earlier positions are lost, so you cannot list the decodings.
  • The shift must happen after cur uses next2.
  • Easy to initialise next2 incorrectly (it must not count when there is no second digit).

Interviewer cross-questions

Why is next2 = 0 at the start?

Say: Position n + 1 does not exist. The pair test requires i + 1 < s.length, so next2 is never added at the last digit, and 0 is a safe placeholder.

How would you also print the decodings?

Say: Use backtracking (or keep the full table and walk it) because the number of decodings can be exponential; counting is cheap, listing is not.

What happens with very long inputs?

Say: The count can exceed 32 bits; the problem guarantees it fits. In general use 64-bit or modular arithmetic.

Synchronized code walkthrough

Showing: Plain recursion — shares the player above; click any step to jump.

int numDecodings(string s) {
    function<int(int)> ways = [&](int i) -> int {
        if (i == (int)s.size()) return 1;
        if (s[i] == '0') return 0;
        int total = ways(i + 1);
        if (i + 1 < (int)s.size() && stoi(s.substr(i, 2)) <= 26) total += ways(i + 2);
        return total;
    };
    return ways(0);
}