Loading…

mediumDynamic ProgrammingLC #91Frequently asked

Decode Ways

Q: How do you solve Decode Ways using the Top-Down Recursion (Exponential, No Memo) approach?

When to use it: Open with this to expose the overlapping-subproblems structure — it justifies memoization as the next step. Define `decode(i)` as the number of ways to decode the suffix starting at index `i`. Recurse: try the single-digit step to `decode(i+1)` when `s[i] != '0'`, and the two-digit step to `decode(i+2)` when `s[i..i+1]` is in 10–26. Sum the valid branches. **Why frame it on the suffix.** Decoding is a left-to-right commitment: once you decide how to consume the front, the rest is the *same kind* of subproblem on a shorter string. That self-similarity — 'the answer for s[i:] is built from the answers for s[i+1:] and s[i+2:]' — is the signature of DP. Writing it as `decode(i)` over an index makes the recursion and later the memo table fall out naturally. **The two base cases that carry the correctness.** First, `decode(n) = 1`: running off the end means you successfully partitioned the whole string, which is one valid decoding (the empty tail). Returning 0 here would zero out every count. Second, `s[i] == '0'`: no letter maps from a group with a leading zero, so this branch contributes nothing — return 0 immediately. Get these two wrong and every downstream number is wrong. **Why this version is exponential.** `decode(i)` for a given `i` gets recomputed every time a different path reaches index `i` — and many paths do. The call tree fans out like Fibonacci's, which is exponential. That repeated work is the cue to memoize: the answer for each `i` is fixed, so compute it once and cache it. Time complexity: O(2ⁿ). Space complexity: O(n).

Q: How do you solve Decode Ways using the Top-Down with Memoization approach?

When to use it: The natural fix once you've named the overlapping subproblems. Say 'each decode(i) is fixed, so cache it'. Same recurrence as above, but cache `decode(i)` the first time it's computed. Subsequent calls for the same `i` return instantly. **Why this is the minimal change with maximal payoff.** The recursion was correct; it was just wasteful. Memoization adds a single array and two lines — check the cache on entry, write it on exit — and converts the exponential Fibonacci tree into a linear walk. There are only `n + 1` distinct index arguments, so once each is solved the total work is `O(n)`. This is the classic 'top-down DP = recursion + a memo' move, and it's worth doing explicitly in an interview to show you understand *why* it's fast, not just that it is. **Why a sentinel, not zero, for 'uncomputed'.** Zero is a *legitimate* answer (e.g. `decode` of a string starting with '0' is 0). If you initialize the memo to 0 and use 0 to mean 'not computed yet', you'll never cache those genuinely-zero results and may recompute or, worse, misread state. Initialize to `-1` (impossible as a count) so 'uncomputed' is unambiguous. **Why people stop here — and why we don't.** Memoized top-down is clean, easy to derive from the recursion, and fully O(n). It's a perfectly good interview answer. But each `decode(i)` only ever needs `decode(i+1)` and `decode(i+2)` — two states. That observation is the bridge to the O(1)-space tabulation, which also drops the recursion stack. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Decode Ways using the Bottom-Up, O(1) Space (Optimal) approach?

When to use it: The answer they want. Pitch it as 'I only need the last two counts, so two integers replace the whole array'. Because `dp[i]` needs only `dp[i+1]` and `dp[i+2]`, the whole array is overkill — keep just those two values in scalars and roll them forward as you scan. **The space collapse, made concrete.** Think of two variables: `oneAhead` = ways to decode the suffix starting one position ahead, and `twoAhead` = two positions ahead. For the current index `i`, the new count is `(s[i] != '0' ? oneAhead : 0) + (s[i..i+1] in 10..26 ? twoAhead : 0)`. Then shift: `twoAhead = oneAhead`, `oneAhead = current`. After scanning every index, `oneAhead` holds the answer for the full string. This is the same trick that turns Fibonacci's array into two variables — it works because the dependency window is fixed at width two. **Why iterate from the end.** Defining `dp[i]` over the *suffix* makes `dp[n] = 1` (empty suffix) and `dp[n+1] = 0` the clean seeds, and each step looks *forward* to already-computed values. You can equally iterate front-to-back with a prefix formulation; the suffix version just maps most directly onto the recursion we built, which keeps the validity gates identical and reduces the chance of an off-by-one. **Where the bug always hides.** Every wrong submission of Decode Ways dies on the same two checks: the single-digit step must be skipped when `s[i] == '0'` (zero ways through that branch), and the two-digit step must be gated to the inclusive range 10–26. Because `s[i] != '0'` is already enforced for the single step, the two-digit value is automatically ≥ 10 when `s[i]` is 1 or 2 — so the real test reduces to 'first digit is 1, or (first digit is 2 and second ≤ 6)'. Keep those gates exact and the rolling scan is bulletproof. Time complexity: O(n). Space complexity: O(1).

LCPractice

Dynamic Programming · 8 of 44 · 9 min

A message containing letters from A-Z is encoded to numbers using the mapping 'A' -> "1", 'B' -> "2", …, 'Z' -> "26".

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of this mapping (there may be multiple valid groupings).

Given a string s containing only digits, return the number of ways to decode it. Note that '06' cannot map to 'F' because '6' is different from '06'. The answer fits in a 32-bit integer.

In plain English

Read the digit string left to right; at each point you may consume one digit (if it's 1–9) or two digits (if they form 10–26) as a single letter. Count how many complete groupings exist. A '0' can only ever be the second digit of '10' or '20' — never stand alone.

Examples

Example 1

Input: s = "12"
Output: 2
Note: "12" can be "AB" (1, 2) or "L" (12). Two ways.

Example 2

Input: s = "226"
Output: 3
Note: "BZ" (2,26), "VF" (22,6), "BBF" (2,2,6). Three ways.

Example 3

Input: s = "06"
Output: 0
Note: Leading '0' can't start a group, and '06' isn't a valid two-digit letter. Zero ways.

Constraints

1 ≤ s.length ≤ 100
s contains only digits and may contain leading zeros
A grouping starting with '0' is invalid (no letter maps to 0 or to '0x')
Valid two-digit groups are exactly '10' through '26'

Clarifying questions4First question: Can the string contain a '0'?Explore questions

Q1.Can the string contain a '0'?
Yes, and it's the crux. A '0' is only decodable as part of '10' or '20'. A leading '0' or a '0' not preceded by 1 or 2 means zero ways.
Q2.Is '06' a valid encoding of 'F'?
No. Groups can't have leading zeros — '6' decodes to 'F', but '06' decodes to nothing.
Q3.Do I return the count or the actual decodings?
The count. Listing them would be exponential; the prompt asks how many, which is a DP.
Q4.What's the empty-string convention?
An empty suffix has exactly one decoding (the empty one). That's the base case that seeds the recurrence; the input itself is guaranteed non-empty.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count how many ways a digit string maps back to letters under A=1…Z=26. It's a 1-D DP that mirrors Fibonacci: ways(i) = (one-digit valid ? ways(i+1) : 0) + (two-digit 10–26 ? ways(i+2) : 0). The optimal version rolls the two trailing states into two integers — O(n) time, O(1) space — with the whole problem hinging on correctly handling the '0' digit.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize a counting DP with bounded look-ahead (climbing-stairs shape) and whether you handle the '0' digit and the 10–26 two-digit window precisely — that's where almost everyone breaks.

Where candidates slip

Treating any two-digit pair as valid (counting '27' or '09'), or forgetting that a standalone '0' kills a branch, producing off-by-one or wildly wrong counts.

How to stand out

Name it as Fibonacci-with-gates, write the recurrence on s[i:] cleanly, then collapse the array to two rolling integers and explain why only the last two states matter.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Top-Down Recursion (Exponential, No Memo)	`O(2ⁿ)`	`O(n)`	Open with this to expose the overlapping-subproblems structure — it justifies memoization as the next step.	Read
2	Top-Down with Memoization	`O(n)`	`O(n)`	The natural fix once you've named the overlapping subproblems. Say 'each decode(i) is fixed, so cache it'.	Read
3	Bottom-Up, O(1) Space (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Pitch it as 'I only need the last two counts, so two integers replace the whole array'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCount decodings of a digit stringHow much memory?Cleanest to reasonClassic tableExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Top-Down Recursion (Exponential, No Memo)

TimeO(2ⁿ)SpaceO(n)

Open with this to expose the overlapping-subproblems structure — it justifies memoization as the next step.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At index i you face a choice: decode one digit, or decode two if they form 10–26. How many total ways follow from each choice?

2Hint 2Explore hint

Define decode(i) = number of ways to decode the suffix s[i:]. It's the sum of decode(i+1) (if one digit valid) and decode(i+2) (if two digits valid).

3Hint 3Explore hint

Base case: reaching the end (i == n) is one complete decoding → return 1. Hitting a leading '0' → return 0, that branch is dead.

A · Core idea

Define decode(i) as the number of ways to decode the suffix starting at index i. Recurse: try the single-digit step to decode(i+1) when s[i] != '0', and the two-digit step to decode(i+2) when s[i..i+1] is in 10–26. Sum the valid branches.

Why frame it on the suffix. Decoding is a left-to-right commitment: once you decide how to consume the front, the rest is the same kind of subproblem on a shorter string. That self-similarity — 'the answer for s[i:] is built from the answers for s[i+1:] and s[i+2:]' — is the signature of DP. Writing it as decode(i) over an index makes the recursion and later the memo table fall out naturally.

The two base cases that carry the correctness. First, decode(n) = 1: running off the end means you successfully partitioned the whole string, which is one valid decoding (the empty tail). Returning 0 here would zero out every count. Second, s[i] == '0': no letter maps from a group with a leading zero, so this branch contributes nothing — return 0 immediately. Get these two wrong and every downstream number is wrong.

Why this version is exponential. decode(i) for a given i gets recomputed every time a different path reaches index i — and many paths do. The call tree fans out like Fibonacci's, which is exponential. That repeated work is the cue to memoize: the answer for each i is fixed, so compute it once and cache it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "12"

Array state

decode(0)

'2'→decode(1); '22'≤26→decode(2)

i ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

Reference implementation previewpublic int numDecodings(String s) { return decode(s, 0); } private int decode(String s, int i) {Explore the full code

solution.javaJava

Top-Down Recursion (Exponential, No Memo) — reference

3 teaching notes

1
public int numDecodings(String s) {
2
    return decode(s, 0);
3
}
4
 
5
private int decode(String s, int i) {
6
    // Reaching the end = one valid decoding. The seed of the whole recurrence.
7
    if (i == s.length()) return 1;
8
    // A group can't start with 0, so this branch is dead.
9
    if (s.charAt(i) == '0') return 0;
10
    int ways = decode(s, i + 1);
11
    if (i + 1 < s.length()) {
12
        int two = Integer.parseInt(s.substring(i, i + 2));
13
        // Two-digit step only when 10–26 (s[i] != '0' already guaranteed above).
14
        if (two <= 26) ways += decode(s, i + 2);
15
    }
16
    return ways;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The recursion tree is literally Fibonacci-shaped: decode(i) calls decode(i+1) and decode(i+2). Fibonacci recomputed naively is O(2ⁿ); cached it's O(n). Spotting that shape tells you immediately that a memo (or two rolling variables) collapses the cost.

ComplexityO(2ⁿ) time, O(n) space — Each call can branch into two, and the recursion depth is n, so without memo the tree has up to O(2ⁿ) nodes. Stack depth is O(n).

E · Edge cases and pitfalls4s = "0" — decode(0) sees s[0]=='0' → returns 0 immediately. Leading zero is undecodable.Explore edge cases

Edge cases handled

s = "0"decode(0) sees s[0]=='0' → returns 0 immediately. Leading zero is undecodable.

Pitfalls

Returning 0 at i == n instead of 1 — zeros out every count.
Skipping the s[i] == '0' guard, so '0' branches get counted as decodable.
Not bounds-checking i+1 before reading the two-digit group — index out of range on the last character.

03.2

Approach 2 of 3

Top-Down with Memoization

TimeO(n)SpaceO(n)

The natural fix once you've named the overlapping subproblems. Say 'each decode(i) is fixed, so cache it'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You just saw decode(i) get recomputed for the same i along different paths. What if you stored each result the first time you compute it?

2Hint 2Explore hint

Add a memo array of size n+1 (or a hash map) keyed by i, initialized to a sentinel like -1. Return the cached value if present.

3Hint 3Explore hint

With memoization each index is computed once; the rest are O(1) lookups, dropping the total to O(n).

A · Core idea

Same recurrence as above, but cache decode(i) the first time it's computed. Subsequent calls for the same i return instantly.

Why this is the minimal change with maximal payoff. The recursion was correct; it was just wasteful. Memoization adds a single array and two lines — check the cache on entry, write it on exit — and converts the exponential Fibonacci tree into a linear walk. There are only n + 1 distinct index arguments, so once each is solved the total work is O(n). This is the classic 'top-down DP = recursion + a memo' move, and it's worth doing explicitly in an interview to show you understand why it's fast, not just that it is.

Why a sentinel, not zero, for 'uncomputed'. Zero is a legitimate answer (e.g. decode of a string starting with '0' is 0). If you initialize the memo to 0 and use 0 to mean 'not computed yet', you'll never cache those genuinely-zero results and may recompute or, worse, misread state. Initialize to -1 (impossible as a count) so 'uncomputed' is unambiguous.

Why people stop here — and why we don't. Memoized top-down is clean, easy to derive from the recursion, and fully O(n). It's a perfectly good interview answer. But each decode(i) only ever needs decode(i+1) and decode(i+2) — two states. That observation is the bridge to the O(1)-space tabulation, which also drops the recursion stack.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "226"

Array state

after decode(3)

base case cached

-1

[0]

-1

[1]

-1

[2]

[3]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int numDecodings(String s) { int[] memo = new int[s.length() + 1]; Arrays.fill(memo, -1); return decode(s, 0, memo); }Explore the full code

solution.javaJava

Top-Down with Memoization — reference

3 teaching notes

1
public int numDecodings(String s) {
2
    int[] memo = new int[s.length() + 1];
3
    // -1 marks 'uncomputed' so a genuine 0 result is still cached correctly.
4
    Arrays.fill(memo, -1);
5
    return decode(s, 0, memo);
6
}
7
 
8
private int decode(String s, int i, int[] memo) {
9
    if (i == s.length()) return 1;
10
    if (s.charAt(i) == '0') return 0;
11
    // Cache hit — return without re-expanding the subtree. This is what makes it O(n).
12
    if (memo[i] != -1) return memo[i];
13
    int ways = decode(s, i + 1, memo);
14
    if (i + 1 < s.length() && Integer.parseInt(s.substring(i, i + 2)) <= 26) {
15
        ways += decode(s, i + 2, memo);
16
    }
17
    // Store before returning so future calls at this index are O(1).
18
    memo[i] = ways;
19
    return ways;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Top-down DP is just the brute-force recursion plus a cache. The recurrence didn't change; only the bookkeeping did. Recognizing that a function of a single small index has a fixed answer is the whole justification for the memo.

ComplexityO(n) time, O(n) space — Each of the n+1 indices is computed exactly once (O(1) work per index after children are cached) → O(n) time. The memo and recursion stack are O(n) space.

E · Edge cases and pitfalls4s = "100" — decode(1) sees the second char '0' is decodable only as part of '10' via the two-digit step from index 0; the trailing '0' at index 2 has no valid single or two-digit group → total 0.Explore edge cases

Edge cases handled

s = "100"decode(1) sees the second char '0' is decodable only as part of '10' via the two-digit step from index 0; the trailing '0' at index 2 has no valid single or two-digit group → total 0.

Pitfalls

Initializing memo to 0 and using 0 as 'uncomputed' — collides with legitimate zero answers.
Forgetting to write memo[i] before returning — silently degrades back to exponential.
Caching the '0' short-circuit return is unnecessary but harmless; the guard runs before the cache check.

03.3

Approach 3 of 3 · Optimal

Bottom-Up, O(1) Space (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Pitch it as 'I only need the last two counts, so two integers replace the whole array'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the recurrence: dp[i] depends only on dp[i+1] and dp[i+2]. How many past values do you ever actually need?

2Hint 2Explore hint

Just two. Replace the dp[] array with two rolling integers — the count for the position one ahead and two ahead.

3Hint 3Explore hint

Iterate from the end (or the front) carrying those two values forward, applying the same single/double validity gates each step.

A · Core idea

Because dp[i] needs only dp[i+1] and dp[i+2], the whole array is overkill — keep just those two values in scalars and roll them forward as you scan.

The space collapse, made concrete. Think of two variables: oneAhead = ways to decode the suffix starting one position ahead, and twoAhead = two positions ahead. For the current index i, the new count is (s[i] != '0' ? oneAhead : 0) + (s[i..i+1] in 10..26 ? twoAhead : 0). Then shift: twoAhead = oneAhead, oneAhead = current. After scanning every index, oneAhead holds the answer for the full string. This is the same trick that turns Fibonacci's array into two variables — it works because the dependency window is fixed at width two.

Why iterate from the end. Defining dp[i] over the suffix makes dp[n] = 1 (empty suffix) and dp[n+1] = 0 the clean seeds, and each step looks forward to already-computed values. You can equally iterate front-to-back with a prefix formulation; the suffix version just maps most directly onto the recursion we built, which keeps the validity gates identical and reduces the chance of an off-by-one.

Where the bug always hides. Every wrong submission of Decode Ways dies on the same two checks: the single-digit step must be skipped when s[i] == '0' (zero ways through that branch), and the two-digit step must be gated to the inclusive range 10–26. Because s[i] != '0' is already enforced for the single step, the two-digit value is automatically ≥ 10 when s[i] is 1 or 2 — so the real test reduces to 'first digit is 1, or (first digit is 2 and second ≤ 6)'. Keep those gates exact and the rolling scan is bulletproof.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "226"

Array state

i=2

'6' single only → cur=1

[0]

[1]

i ↓

[2]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Bottom-Up, O(1) Space (Optimal) — optimal

4 teaching notes

1
public int numDecodings(String s) {
2
    int n = s.length();
3
    // Empty suffix has exactly one decoding — the seed that makes the counts come out
4
    // right.
5
    int oneAhead = 1; // dp[n]
6
    int twoAhead = 0; // dp[n+1]
7
    for (int i = n - 1; i >= 0; i--) {
8
        int cur = 0;
9
        // If the current digit is '0' it can't start any group, so cur stays 0.
10
        if (s.charAt(i) != '0') {
11
            cur += oneAhead;
12
            // Two-digit step; lower bound 10 is implied because s[i] != '0' here.
13
            if (i + 1 < n && Integer.parseInt(s.substring(i, i + 2)) <= 26) {
14
                cur += twoAhead;
15
            }
16
        }
17
        twoAhead = oneAhead;
18
        // Roll the window forward; after the last iteration oneAhead is the answer.
19
        oneAhead = cur;
20
    }
21
    return oneAhead;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Whenever a DP recurrence reaches back a fixed, small number of steps, the array is a luxury — you only need a sliding window of that many scalars. Decode Ways needs two, exactly like climbing stairs and Fibonacci. Seeing 'dp[i] depends on dp[i+1], dp[i+2]' should immediately trigger 'two variables, O(1) space'.

ComplexityO(n) time, O(1) space — One pass over n characters with O(1) work each → O(n) time. Only two integer accumulators are kept → O(1) space.

E · Edge cases and pitfalls5s = "10" — i=1 '0' → single branch blocked, cur=0. i=0 '1': single ok adds oneAhead=0, '10'≤26 adds twoAhead=1 → cur=1. One way ('J').Explore edge cases

Edge cases handled

s = "10"i=1 '0' → single branch blocked, cur=0. i=0 '1': single ok adds oneAhead=0, '10'≤26 adds twoAhead=1 → cur=1. One way ('J').
s = "100"Trailing '0' at i=2 contributes 0 and propagates; the second '0' has no valid two-digit predecessor → final answer 0.

Pitfalls

Seeding oneAhead = 0 instead of 1 — collapses every count to zero.
Letting the two-digit step fire when s[i] == '0' — '07' would wrongly count; the != '0' guard prevents it.
Treating two-digit values like '27'–'99' as valid by skipping the ≤ 26 check.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int numDecodings(String s) { int n = s.length(); int oneAhead = 1; // dp[n] int twoAhead = 0; // dp[n+1] for (int i = n - 1; i >= 0; i--) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Treating any two digits as valid

Only 10–26 map to a letter. Counting '27', '30', or '09' inflates the answer and silently breaks otherwise-correct DP.

Explore the code comparison

Don't write this

if i + 1 < n:            # any two digits accepted
    cur += two_ahead

Write this instead

if i + 1 < n and int(s[i:i + 2]) <= 26:  # s[i] != '0' already ensures >= 10
    cur += two_ahead

Wrong base case

The empty suffix has exactly one decoding (the empty one). Seeding dp[n] = 0 multiplies through and zeros every count.

Explore the code comparison

Don't write this

int oneAhead = 0; // dp[n] -- WRONG

Write this instead

int oneAhead = 1; // dp[n] -- empty suffix decodes one way

Ignoring the leading-zero gate

If s[i] == '0', no group can start here, so the single-digit branch must contribute 0. Omitting the guard counts impossible decodings.

Explore the code comparison

Don't write this

cur += oneAhead; // even when s.charAt(i) == '0'

Write this instead

if (s.charAt(i) != '0') {
    cur += oneAhead;
    // ... two-digit step
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fibonacci-style 1-D DP with validity gates

Code pattern to memorize

dp[i] = ways to decode s[i:]
dp[n] = 1
dp[i] = (s[i] != '0') * dp[i+1]
      + (10 <= int(s[i:i+2]) <= 26) * dp[i+2]

Rules to remember

1A leading '0' decodes to nothing — '0', '06', and any group starting with 0 contribute 0 ways.
2The two-digit step is valid only for 10–26 inclusive; '27' and '09' are not letters.
3Base case: an empty suffix has exactly 1 decoding (the empty decoding), not 0 — this seeds the recurrence.
4It's Fibonacci with gates: each position adds the next-one-over and next-two-over counts, but only when the digit(s) form a valid letter.
5Multiply, don't add, the branches — ways = single_valid·dp[i+1] + double_valid·dp[i+2]; never count an invalid branch as 1.

Use this pattern when

Count the number of ways to segment / partition a sequence under local rules
Each position's answer depends on the next 1–2 positions (bounded look-ahead)
Choices are 'take one' vs 'take two' with a validity constraint, like climbing-stairs
You only ever need the last two computed states → O(1) space

Choose another pattern when

Need to LIST every decoding, not count → backtracking, exponential output
Look-back window is unbounded → general DP, not the two-state roll
No validity gate (every step always allowed) → plain Fibonacci / climbing stairs
Mapping is many-to-many or ambiguous beyond two digits → different recurrence

Interview takeaway

Decode Ways is climbing-stairs in disguise: from each index you can take a 1-digit or 2-digit step, and you sum the ways from where those steps land — but each step is gated by 'is this a valid letter?'. Nail the '0' handling and the rest is Fibonacci.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFibonacci-style 1-D Counting DP with validity gates. Whenever each position's answer sums a fixed number of look-ahead states under local constraints, write the recurrence, memoize, then roll to O(1) space. Same skeleton as Climbing Stairs and House Robber.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Decode Ways II
Coming soon
The '*' wildcard can be any digit 1–9 — multiply branch counts by how many digits each wildcard allows, mod 1e9+7.
Climbing Stairs
The same two-step recurrence with no validity gate — pure Fibonacci.
Unique Paths
Counting DP in 2-D; each cell sums the two cells it can come from, like this one in one dimension.
Decode Ways (recursion → memo → table)
Practice converting your own top-down memo into the O(1)-space rolling form — the canonical DP-evolution drill.

Same pattern

←

Palindromic Substrings

Continue · Next problem

Longest Increasing Subsequence

mediumDynamic ProgrammingLC #91Frequently asked

Decode Ways

LCPractice

Dynamic Programming · 8 of 44 · 9 min

A message containing letters from A-Z is encoded to numbers using the mapping 'A' -> "1", 'B' -> "2", …, 'Z' -> "26".

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of this mapping (there may be multiple valid groupings).

In plain English

Examples

Example 1

Input: s = "12"
Output: 2
Note: "12" can be "AB" (1, 2) or "L" (12). Two ways.

Example 2

Input: s = "226"
Output: 3
Note: "BZ" (2,26), "VF" (22,6), "BBF" (2,2,6). Three ways.

Example 3

Input: s = "06"
Output: 0
Note: Leading '0' can't start a group, and '06' isn't a valid two-digit letter. Zero ways.

Constraints

1 ≤ s.length ≤ 100
s contains only digits and may contain leading zeros
A grouping starting with '0' is invalid (no letter maps to 0 or to '0x')
Valid two-digit groups are exactly '10' through '26'

Clarifying questions4First question: Can the string contain a '0'?Explore questions

Q1.Can the string contain a '0'?
Yes, and it's the crux. A '0' is only decodable as part of '10' or '20'. A leading '0' or a '0' not preceded by 1 or 2 means zero ways.
Q2.Is '06' a valid encoding of 'F'?
No. Groups can't have leading zeros — '6' decodes to 'F', but '06' decodes to nothing.
Q3.Do I return the count or the actual decodings?
The count. Listing them would be exponential; the prompt asks how many, which is a DP.
Q4.What's the empty-string convention?
An empty suffix has exactly one decoding (the empty one). That's the base case that seeds the recurrence; the input itself is guaranteed non-empty.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Treating any two-digit pair as valid (counting '27' or '09'), or forgetting that a standalone '0' kills a branch, producing off-by-one or wildly wrong counts.

How to stand out

Name it as Fibonacci-with-gates, write the recurrence on s[i:] cleanly, then collapse the array to two rolling integers and explain why only the last two states matter.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Top-Down Recursion (Exponential, No Memo)	`O(2ⁿ)`	`O(n)`	Open with this to expose the overlapping-subproblems structure — it justifies memoization as the next step.	Read
2	Top-Down with Memoization	`O(n)`	`O(n)`	The natural fix once you've named the overlapping subproblems. Say 'each decode(i) is fixed, so cache it'.	Read
3	Bottom-Up, O(1) Space (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Pitch it as 'I only need the last two counts, so two integers replace the whole array'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Top-Down Recursion (Exponential, No Memo)

TimeO(2ⁿ)SpaceO(n)

Open with this to expose the overlapping-subproblems structure — it justifies memoization as the next step.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At index i you face a choice: decode one digit, or decode two if they form 10–26. How many total ways follow from each choice?

2Hint 2Explore hint

Define decode(i) = number of ways to decode the suffix s[i:]. It's the sum of decode(i+1) (if one digit valid) and decode(i+2) (if two digits valid).

3Hint 3Explore hint

Base case: reaching the end (i == n) is one complete decoding → return 1. Hitting a leading '0' → return 0, that branch is dead.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "12"

Array state

decode(0)

'2'→decode(1); '22'≤26→decode(2)

i ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

Reference implementation previewpublic int numDecodings(String s) { return decode(s, 0); } private int decode(String s, int i) {Explore the full code

solution.javaJava

Top-Down Recursion (Exponential, No Memo) — reference

3 teaching notes

1
public int numDecodings(String s) {
2
    return decode(s, 0);
3
}
4
 
5
private int decode(String s, int i) {
6
    // Reaching the end = one valid decoding. The seed of the whole recurrence.
7
    if (i == s.length()) return 1;
8
    // A group can't start with 0, so this branch is dead.
9
    if (s.charAt(i) == '0') return 0;
10
    int ways = decode(s, i + 1);
11
    if (i + 1 < s.length()) {
12
        int two = Integer.parseInt(s.substring(i, i + 2));
13
        // Two-digit step only when 10–26 (s[i] != '0' already guaranteed above).
14
        if (two <= 26) ways += decode(s, i + 2);
15
    }
16
    return ways;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2ⁿ) time, O(n) space — Each call can branch into two, and the recursion depth is n, so without memo the tree has up to O(2ⁿ) nodes. Stack depth is O(n).

E · Edge cases and pitfalls4s = "0" — decode(0) sees s[0]=='0' → returns 0 immediately. Leading zero is undecodable.Explore edge cases

Edge cases handled

s = "0"decode(0) sees s[0]=='0' → returns 0 immediately. Leading zero is undecodable.

Pitfalls

Returning 0 at i == n instead of 1 — zeros out every count.
Skipping the s[i] == '0' guard, so '0' branches get counted as decodable.
Not bounds-checking i+1 before reading the two-digit group — index out of range on the last character.

03.2

Approach 2 of 3

Top-Down with Memoization

TimeO(n)SpaceO(n)

The natural fix once you've named the overlapping subproblems. Say 'each decode(i) is fixed, so cache it'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You just saw decode(i) get recomputed for the same i along different paths. What if you stored each result the first time you compute it?

2Hint 2Explore hint

Add a memo array of size n+1 (or a hash map) keyed by i, initialized to a sentinel like -1. Return the cached value if present.

3Hint 3Explore hint

With memoization each index is computed once; the rest are O(1) lookups, dropping the total to O(n).

A · Core idea

Same recurrence as above, but cache decode(i) the first time it's computed. Subsequent calls for the same i return instantly.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "226"

Array state

after decode(3)

base case cached

-1

[0]

-1

[1]

-1

[2]

[3]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int numDecodings(String s) { int[] memo = new int[s.length() + 1]; Arrays.fill(memo, -1); return decode(s, 0, memo); }Explore the full code

solution.javaJava

Top-Down with Memoization — reference

3 teaching notes

1
public int numDecodings(String s) {
2
    int[] memo = new int[s.length() + 1];
3
    // -1 marks 'uncomputed' so a genuine 0 result is still cached correctly.
4
    Arrays.fill(memo, -1);
5
    return decode(s, 0, memo);
6
}
7
 
8
private int decode(String s, int i, int[] memo) {
9
    if (i == s.length()) return 1;
10
    if (s.charAt(i) == '0') return 0;
11
    // Cache hit — return without re-expanding the subtree. This is what makes it O(n).
12
    if (memo[i] != -1) return memo[i];
13
    int ways = decode(s, i + 1, memo);
14
    if (i + 1 < s.length() && Integer.parseInt(s.substring(i, i + 2)) <= 26) {
15
        ways += decode(s, i + 2, memo);
16
    }
17
    // Store before returning so future calls at this index are O(1).
18
    memo[i] = ways;
19
    return ways;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Each of the n+1 indices is computed exactly once (O(1) work per index after children are cached) → O(n) time. The memo and recursion stack are O(n) space.

Edge cases handled

s = "100"decode(1) sees the second char '0' is decodable only as part of '10' via the two-digit step from index 0; the trailing '0' at index 2 has no valid single or two-digit group → total 0.

Pitfalls

Initializing memo to 0 and using 0 as 'uncomputed' — collides with legitimate zero answers.
Forgetting to write memo[i] before returning — silently degrades back to exponential.
Caching the '0' short-circuit return is unnecessary but harmless; the guard runs before the cache check.

03.3

Approach 3 of 3 · Optimal

Bottom-Up, O(1) Space (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Pitch it as 'I only need the last two counts, so two integers replace the whole array'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the recurrence: dp[i] depends only on dp[i+1] and dp[i+2]. How many past values do you ever actually need?

2Hint 2Explore hint

Just two. Replace the dp[] array with two rolling integers — the count for the position one ahead and two ahead.

3Hint 3Explore hint

Iterate from the end (or the front) carrying those two values forward, applying the same single/double validity gates each step.

A · Core idea

Because dp[i] needs only dp[i+1] and dp[i+2], the whole array is overkill — keep just those two values in scalars and roll them forward as you scan.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "226"

Array state

i=2

'6' single only → cur=1

[0]

[1]

i ↓

[2]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Bottom-Up, O(1) Space (Optimal) — optimal

4 teaching notes

1
public int numDecodings(String s) {
2
    int n = s.length();
3
    // Empty suffix has exactly one decoding — the seed that makes the counts come out
4
    // right.
5
    int oneAhead = 1; // dp[n]
6
    int twoAhead = 0; // dp[n+1]
7
    for (int i = n - 1; i >= 0; i--) {
8
        int cur = 0;
9
        // If the current digit is '0' it can't start any group, so cur stays 0.
10
        if (s.charAt(i) != '0') {
11
            cur += oneAhead;
12
            // Two-digit step; lower bound 10 is implied because s[i] != '0' here.
13
            if (i + 1 < n && Integer.parseInt(s.substring(i, i + 2)) <= 26) {
14
                cur += twoAhead;
15
            }
16
        }
17
        twoAhead = oneAhead;
18
        // Roll the window forward; after the last iteration oneAhead is the answer.
19
        oneAhead = cur;
20
    }
21
    return oneAhead;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One pass over n characters with O(1) work each → O(n) time. Only two integer accumulators are kept → O(1) space.

E · Edge cases and pitfalls5s = "10" — i=1 '0' → single branch blocked, cur=0. i=0 '1': single ok adds oneAhead=0, '10'≤26 adds twoAhead=1 → cur=1. One way ('J').Explore edge cases

Edge cases handled

s = "10"i=1 '0' → single branch blocked, cur=0. i=0 '1': single ok adds oneAhead=0, '10'≤26 adds twoAhead=1 → cur=1. One way ('J').
s = "100"Trailing '0' at i=2 contributes 0 and propagates; the second '0' has no valid two-digit predecessor → final answer 0.

Pitfalls

Seeding oneAhead = 0 instead of 1 — collapses every count to zero.
Letting the two-digit step fire when s[i] == '0' — '07' would wrongly count; the != '0' guard prevents it.
Treating two-digit values like '27'–'99' as valid by skipping the ≤ 26 check.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int numDecodings(String s) { int n = s.length(); int oneAhead = 1; // dp[n] int twoAhead = 0; // dp[n+1] for (int i = n - 1; i >= 0; i--) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Treating any two digits as valid

Only 10–26 map to a letter. Counting '27', '30', or '09' inflates the answer and silently breaks otherwise-correct DP.

Explore the code comparison

Don't write this

if i + 1 < n:            # any two digits accepted
    cur += two_ahead

Write this instead

if i + 1 < n and int(s[i:i + 2]) <= 26:  # s[i] != '0' already ensures >= 10
    cur += two_ahead

Wrong base case

The empty suffix has exactly one decoding (the empty one). Seeding dp[n] = 0 multiplies through and zeros every count.

Explore the code comparison

Don't write this

int oneAhead = 0; // dp[n] -- WRONG

Write this instead

int oneAhead = 1; // dp[n] -- empty suffix decodes one way

Ignoring the leading-zero gate

If s[i] == '0', no group can start here, so the single-digit branch must contribute 0. Omitting the guard counts impossible decodings.

Explore the code comparison

Don't write this

cur += oneAhead; // even when s.charAt(i) == '0'

Write this instead

if (s.charAt(i) != '0') {
    cur += oneAhead;
    // ... two-digit step
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fibonacci-style 1-D DP with validity gates

Code pattern to memorize

dp[i] = ways to decode s[i:]
dp[n] = 1
dp[i] = (s[i] != '0') * dp[i+1]
      + (10 <= int(s[i:i+2]) <= 26) * dp[i+2]

Rules to remember

1A leading '0' decodes to nothing — '0', '06', and any group starting with 0 contribute 0 ways.
2The two-digit step is valid only for 10–26 inclusive; '27' and '09' are not letters.
3Base case: an empty suffix has exactly 1 decoding (the empty decoding), not 0 — this seeds the recurrence.
4It's Fibonacci with gates: each position adds the next-one-over and next-two-over counts, but only when the digit(s) form a valid letter.
5Multiply, don't add, the branches — ways = single_valid·dp[i+1] + double_valid·dp[i+2]; never count an invalid branch as 1.

Use this pattern when

Count the number of ways to segment / partition a sequence under local rules
Each position's answer depends on the next 1–2 positions (bounded look-ahead)
Choices are 'take one' vs 'take two' with a validity constraint, like climbing-stairs
You only ever need the last two computed states → O(1) space

Choose another pattern when

Need to LIST every decoding, not count → backtracking, exponential output
Look-back window is unbounded → general DP, not the two-state roll
No validity gate (every step always allowed) → plain Fibonacci / climbing stairs
Mapping is many-to-many or ambiguous beyond two digits → different recurrence

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Decode Ways II
Coming soon
The '*' wildcard can be any digit 1–9 — multiply branch counts by how many digits each wildcard allows, mod 1e9+7.
Climbing Stairs
The same two-step recurrence with no validity gate — pure Fibonacci.
Unique Paths
Counting DP in 2-D; each cell sums the two cells it can come from, like this one in one dimension.
Decode Ways (recursion → memo → table)
Practice converting your own top-down memo into the O(1)-space rolling form — the canonical DP-evolution drill.

Same pattern

←

Palindromic Substrings

Continue · Next problem

Longest Increasing Subsequence