Decode Ways (LeetCode 91)
A digit-only string was produced by encoding letters through the mapping "1" -> 'A', "2" -> 'B', ..., "25" -> 'Y', "26" -> 'Z'. Because some two-digit codes contain smaller valid one-digit codes inside them ("2" and "5" versus "25"), the same digit string can often be split into letters in more than one way.
For example, the digits "11106" can be grouped as (1, 1, 10, 6) to spell "AAJF", or as (11, 10, 6) to spell "KJF". Grouping it as (1, 11, 06) is not allowed, because "06" is not a valid code -- only "6" is.
Given a digit string s, count how many distinct ways it can be decoded this way, returning 0 when no valid decoding exists at all. Inputs are limited so the count always fits in a 32-bit integer.
Worked Examples
s = "12"2s = "226"3s = "06"0⚖️Formal Constraints & Bounds
1 <= s.length <= 100scontains only digits and may contain leading zero(s).
Core Insight
The ways to decode s[index:] depend only on index, never on how the digits before it were split. So dfs(index) is computed once, stored in memo[index], and every other path that reaches the same index reuses it.
Real-World Scenario & Production Applications
Variable-length binary protocol decoding, telephony DTMF sequence parsing.
Subproblems & Recurrence Decomposition3 Phases
dfs(index) answers: how many ways can s[index:] be decoded? The answer depends on index alone, so it can be stored under index.
if index == len(s):
return 1
if s[index] == "0":
return 0Step-by-Step Execution Trace Table
"226" (Root, d=0, Index 0) / \ 1-digit ('2') / \ 2-digits ('22') / \ "26" (d=1, Index 1) "6" (d=1, Index 2) / \ | 1-digit ('2') / 2-digits \ 1-digit ('6') | 1-digit ('6') / ('26') \ | "6" (d=2, Index 2) "" (d=2, Index 3) "" (d=2, Index 3) "" (d=2, Index 3) | ✅ (1 way) ✅ (1 way) ✅ (1 way) 1-digit ('6')| "" (d=3, Index 3) ✅ (1 way) memo[2] = 1 way memo[1] = 1+1 = 2 ways memo[0] = 2+1 = 3 ways Step-by-Step Decision Trace
- Step 1 (Root, d=0, Index 0, "226"):
- Branch 1: Single digit
'2'('B') callsdfs(1). - Branch 2: Double digit
'22'('V', ) callsdfs(2).
- Branch 1: Single digit
- Step 2 (Branch 1: Single digit '2', d=1, Index 1, "26"):
- Branch 1: Single digit
'2'('B') callsdfs(2). - Branch 2: Double digit
'26'('Z', ) callsdfs(3)Base Case (1 way ✅).
- Branch 1: Single digit
- Step 3 (Branch 1: Single digit '2', d=2, Index 2, "6"):
- Single digit
'6'('F') callsdfs(3)Base Case (1 way ✅). - Cache
memo[2] = 1.
- Single digit
- Step 4 (Aggregate Index 1, d=1):
dfs(1) = dfs(2) + dfs(3) = 1 + 1 = 2 ways. Cachememo[1] = 2. - Step 5 (Branch 2: Double digit '22', d=1, Index 2, "6"):
- Single digit
'6'('F') callsdfs(3)Base Case (1 way ✅).
- Single digit
- Step 6 (Aggregate Index 0, d=0):
dfs(0) = dfs(1) + dfs(2) = 2 + 1 = 3 ways. Cachememo[0] = 3. Record Total Valid Decodings: 3 ("BZ","VF","BBF") ✅. Total Valid Decodings: 3 ("BZ","VF","BBF").
| 1 | memo = {} |
| 2 | def dfs(index): |
| 3 | if index == len(s): |
| 4 | return 1 |
| 5 | if s[index] == '0': |
| 6 | return 0 |
| 7 | if index in memo: |
| 8 | return memo[index] |
| 9 | res = dfs(index + 1) |
| 10 | if index + 1 < len(s) and (s[index] == '1' or (s[index] == '2' and s[index + 1] <= '6')): |
| 11 | res += dfs(index + 2) |
| 12 | memo[index] = res |
| 13 | return res |
| 14 | return dfs(0) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A message containing letters from A-Z is encoded to numbers using '1' -> 'A', ..., '26' -> 'Z'. Given a string of digits, how many ways can it be decoded? At any index i, the decoder faces a two-way branch:
- Single-digit branch: Decode
s[i]ifs[i] != '0'. - Double-digit branch: Decode
s[i:i+2]if the two-digit value is between 10 and 26. Digits like '0' have no individual letter mapping and cannot begin a valid two-digit code (e.g. "06" is invalid). Top-down backtracking with memoization counts the total valid leaves in this branching tree in linear time.
🏟️ The Analogy: The Telegraph Operator Reading Morse Numbers
Imagine a telegraph operator receiving a stream of digits on ticker tape: "226". The operator looks at the first digit: "2" can be 'B'. If the operator decodes "2" as 'B', the remaining tape is "26". But "22" could also be 'V'. If the operator decodes "22" as 'V', the remaining tape is "6". At each step, the operator branches into 1-character or 2-character decodings, dropping invalid sequences (like leading zeros) into the wastebasket.
🔑 Why It Works
Notice the base cases: reaching the end of the string (index == len(s)) contributes valid decoding path, while encountering a standalone '0' immediately aborts the branch with ways. Memoizing by index ensures each digit index is processed at most once.
A memo key that misses an argument:
memomust be keyed by every argument that changes the answer. Hereindexalone decides the ways to decodes[index:]; in Interleaving String (LC 97) the answer depends on how far both strings are used, so the key is(i, j), and keying byialone mixes up calls that used different amounts ofs2.Reading a stored 0 as missing:
if memo.get(index):treats a stored0as absent, so everyindexbefore an unreadable"30"is explored again on every call. Testif index in memo:.Returning without storing:
memo[index] = resmust run beforereturn res, or the cache never fills and the run is as slow as the plain recursion (exponential on a long run of"1"s).Leading zero:
'0'has no letter of its own and never starts a two-digit code ('06'is invalid), sodfsreturns0as soon ass[index] == "0".Two-digit range: only
10through26are codes:s[index] == "1", ors[index] == "2"ands[index + 1] <= "6".
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks to "count how many distinct ways" the digits "can be decoded", and says "the same digit string can often be split into letters in more than one way": each position has a one-digit and a two-digit choice, so the plain recursion branches twice per digit and reaches the same index along many different splits. The count for the rest of the string, s[index:], does not depend on how the digits before it were split.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: memo[index] is written only with the finished number of ways to decode s[index:], so every call after the first one for the same index returns it without exploring again. index is the whole key because it is the only argument that changes the answer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Leading zero and range: return
0whens[index] == "0", and read two digits only for 10 to 26 ("06"and"27"are not codes).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use Memoization. The plain recursion is easy: at each index I read one digit, or two digits when they form 10 to 26, and add up the ways from what is left. But it reaches the same index along many different splits, so it is exponential. The number of ways to decode the rest of the string depends only on index, not on how I split the digits before it, so I store dfs(index) in memo the first time it finishes and return it on every later call. The trap is the key: it must hold every argument that changes the answer. Here that is index alone. I also test 'index in memo', because a stored zero is a real answer. Each of the N plus one indices is solved once with constant work, so
O(N)time, and the memo plus the recursion stack takeO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the code: dfs explores (gets past if index in memo) at most once per value of index, 0 to N, because the first call that finishes writes memo[index] = res and every later call for that index returns at the lookup. An exploring call does constant work (two digit checks, one store) and makes at most two calls, dfs(index + 1) and dfs(index + 2). Each of those calls either explores (at most N + 1 of them in total) or returns in O(1). So there are at most N + 1 exploring calls and 2(N + 1) quick ones: O(N).
O(N) memo and recursion stack
Look at the allocations: memo holds at most one entry per index that explores, so at most N entries. The recursion goes one level deeper per digit read, so the call stack is at most N + 1 frames deep. The answer is one integer. Total O(N), memo and recursion stack.
T(N) = (N + 1) exploring calls x O(1) + 2(N + 1) lookups x O(1) = O(N)
Derivation Progression
index in 0..N -> N + 1 values
The answer of dfs(index) depends on index alone, so there are only N + 1 different questions.
memo[index] = res before return res
The first call for an index explores; every later call for it stops at if index in memo and returns the stored value.
O(1) + at most 2 calls
Two digit checks, dfs(index + 1), dfs(index + 2) when the two digits form 10 to 26, and one store.
(N + 1) x O(1) + 2(N + 1) x O(1) = O(N)
At most N + 1 calls explore and each makes at most two calls, so at most 3(N + 1) calls run in all, each doing constant work outside its children.
Variable Definitions
len(s), the number of digits
Memory Architecture & Bounds
O(N): one frame per digit read, at most N + 1 deep
O(N): memo, at most one entry per index
O(1): one integer
Boundary Best / Worst Cases
: s[0] == "0" returns 0 at once
: a string of 1s and 2s, where every index branches twice
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "count how many distinct ways", "can often be split into letters in more than one way". Each digit opens a one-digit and a two-digit branch, and many split paths reach the same index: Memoization, one stored answer per index.
. The plain recursion makes about calls on a run of 1s (317,810 calls for 25 ones); with the memo at most calls run. A recursion depth of 101 frames is far below Python's default limit of 1,000.
Where the cache lives: create memo (or the functools.cache-wrapped dfs) inside numDecodings, so every call starts empty. A module-level cache keeps every earlier string's answers in memory and grows with every call.
Decode Ways (LeetCode 91)
A digit-only string was produced by encoding letters through the mapping "1" -> 'A', "2" -> 'B', ..., "25" -> 'Y', "26" -> 'Z'. Because some two-digit codes contain smaller valid one-digit codes inside them ("2" and "5" versus "25"), the same digit string can often be split into letters in more than one way.
For example, the digits "11106" can be grouped as (1, 1, 10, 6) to spell "AAJF", or as (11, 10, 6) to spell "KJF". Grouping it as (1, 11, 06) is not allowed, because "06" is not a valid code -- only "6" is.
Given a digit string s, count how many distinct ways it can be decoded this way, returning 0 when no valid decoding exists at all. Inputs are limited so the count always fits in a 32-bit integer.
Worked Examples
s = "12"2s = "226"3s = "06"0⚖️Formal Constraints & Bounds
1 <= s.length <= 100scontains only digits and may contain leading zero(s).
Core Insight
The ways to decode s[index:] depend only on index, never on how the digits before it were split. So dfs(index) is computed once, stored in memo[index], and every other path that reaches the same index reuses it.
Real-World Scenario & Production Applications
Variable-length binary protocol decoding, telephony DTMF sequence parsing.
Subproblems & Recurrence Decomposition3 Phases
dfs(index) answers: how many ways can s[index:] be decoded? The answer depends on index alone, so it can be stored under index.
if index == len(s):
return 1
if s[index] == "0":
return 0Step-by-Step Execution Trace Table
"226" (Root, d=0, Index 0) / \ 1-digit ('2') / \ 2-digits ('22') / \ "26" (d=1, Index 1) "6" (d=1, Index 2) / \ | 1-digit ('2') / 2-digits \ 1-digit ('6') | 1-digit ('6') / ('26') \ | "6" (d=2, Index 2) "" (d=2, Index 3) "" (d=2, Index 3) "" (d=2, Index 3) | ✅ (1 way) ✅ (1 way) ✅ (1 way) 1-digit ('6')| "" (d=3, Index 3) ✅ (1 way) memo[2] = 1 way memo[1] = 1+1 = 2 ways memo[0] = 2+1 = 3 ways Step-by-Step Decision Trace
- Step 1 (Root, d=0, Index 0, "226"):
- Branch 1: Single digit
'2'('B') callsdfs(1). - Branch 2: Double digit
'22'('V', ) callsdfs(2).
- Branch 1: Single digit
- Step 2 (Branch 1: Single digit '2', d=1, Index 1, "26"):
- Branch 1: Single digit
'2'('B') callsdfs(2). - Branch 2: Double digit
'26'('Z', ) callsdfs(3)Base Case (1 way ✅).
- Branch 1: Single digit
- Step 3 (Branch 1: Single digit '2', d=2, Index 2, "6"):
- Single digit
'6'('F') callsdfs(3)Base Case (1 way ✅). - Cache
memo[2] = 1.
- Single digit
- Step 4 (Aggregate Index 1, d=1):
dfs(1) = dfs(2) + dfs(3) = 1 + 1 = 2 ways. Cachememo[1] = 2. - Step 5 (Branch 2: Double digit '22', d=1, Index 2, "6"):
- Single digit
'6'('F') callsdfs(3)Base Case (1 way ✅).
- Single digit
- Step 6 (Aggregate Index 0, d=0):
dfs(0) = dfs(1) + dfs(2) = 2 + 1 = 3 ways. Cachememo[0] = 3. Record Total Valid Decodings: 3 ("BZ","VF","BBF") ✅. Total Valid Decodings: 3 ("BZ","VF","BBF").
| 1 | memo = {} |
| 2 | def dfs(index): |
| 3 | if index == len(s): |
| 4 | return 1 |
| 5 | if s[index] == '0': |
| 6 | return 0 |
| 7 | if index in memo: |
| 8 | return memo[index] |
| 9 | res = dfs(index + 1) |
| 10 | if index + 1 < len(s) and (s[index] == '1' or (s[index] == '2' and s[index + 1] <= '6')): |
| 11 | res += dfs(index + 2) |
| 12 | memo[index] = res |
| 13 | return res |
| 14 | return dfs(0) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A message containing letters from A-Z is encoded to numbers using '1' -> 'A', ..., '26' -> 'Z'. Given a string of digits, how many ways can it be decoded? At any index i, the decoder faces a two-way branch:
- Single-digit branch: Decode
s[i]ifs[i] != '0'. - Double-digit branch: Decode
s[i:i+2]if the two-digit value is between 10 and 26. Digits like '0' have no individual letter mapping and cannot begin a valid two-digit code (e.g. "06" is invalid). Top-down backtracking with memoization counts the total valid leaves in this branching tree in linear time.
🏟️ The Analogy: The Telegraph Operator Reading Morse Numbers
Imagine a telegraph operator receiving a stream of digits on ticker tape: "226". The operator looks at the first digit: "2" can be 'B'. If the operator decodes "2" as 'B', the remaining tape is "26". But "22" could also be 'V'. If the operator decodes "22" as 'V', the remaining tape is "6". At each step, the operator branches into 1-character or 2-character decodings, dropping invalid sequences (like leading zeros) into the wastebasket.
🔑 Why It Works
Notice the base cases: reaching the end of the string (index == len(s)) contributes valid decoding path, while encountering a standalone '0' immediately aborts the branch with ways. Memoizing by index ensures each digit index is processed at most once.
A memo key that misses an argument:
memomust be keyed by every argument that changes the answer. Hereindexalone decides the ways to decodes[index:]; in Interleaving String (LC 97) the answer depends on how far both strings are used, so the key is(i, j), and keying byialone mixes up calls that used different amounts ofs2.Reading a stored 0 as missing:
if memo.get(index):treats a stored0as absent, so everyindexbefore an unreadable"30"is explored again on every call. Testif index in memo:.Returning without storing:
memo[index] = resmust run beforereturn res, or the cache never fills and the run is as slow as the plain recursion (exponential on a long run of"1"s).Leading zero:
'0'has no letter of its own and never starts a two-digit code ('06'is invalid), sodfsreturns0as soon ass[index] == "0".Two-digit range: only
10through26are codes:s[index] == "1", ors[index] == "2"ands[index + 1] <= "6".
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks to "count how many distinct ways" the digits "can be decoded", and says "the same digit string can often be split into letters in more than one way": each position has a one-digit and a two-digit choice, so the plain recursion branches twice per digit and reaches the same index along many different splits. The count for the rest of the string, s[index:], does not depend on how the digits before it were split.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: memo[index] is written only with the finished number of ways to decode s[index:], so every call after the first one for the same index returns it without exploring again. index is the whole key because it is the only argument that changes the answer.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Leading zero and range: return
0whens[index] == "0", and read two digits only for 10 to 26 ("06"and"27"are not codes).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use Memoization. The plain recursion is easy: at each index I read one digit, or two digits when they form 10 to 26, and add up the ways from what is left. But it reaches the same index along many different splits, so it is exponential. The number of ways to decode the rest of the string depends only on index, not on how I split the digits before it, so I store dfs(index) in memo the first time it finishes and return it on every later call. The trap is the key: it must hold every argument that changes the answer. Here that is index alone. I also test 'index in memo', because a stored zero is a real answer. Each of the N plus one indices is solved once with constant work, so
O(N)time, and the memo plus the recursion stack takeO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the code: dfs explores (gets past if index in memo) at most once per value of index, 0 to N, because the first call that finishes writes memo[index] = res and every later call for that index returns at the lookup. An exploring call does constant work (two digit checks, one store) and makes at most two calls, dfs(index + 1) and dfs(index + 2). Each of those calls either explores (at most N + 1 of them in total) or returns in O(1). So there are at most N + 1 exploring calls and 2(N + 1) quick ones: O(N).
O(N) memo and recursion stack
Look at the allocations: memo holds at most one entry per index that explores, so at most N entries. The recursion goes one level deeper per digit read, so the call stack is at most N + 1 frames deep. The answer is one integer. Total O(N), memo and recursion stack.
T(N) = (N + 1) exploring calls x O(1) + 2(N + 1) lookups x O(1) = O(N)
Derivation Progression
index in 0..N -> N + 1 values
The answer of dfs(index) depends on index alone, so there are only N + 1 different questions.
memo[index] = res before return res
The first call for an index explores; every later call for it stops at if index in memo and returns the stored value.
O(1) + at most 2 calls
Two digit checks, dfs(index + 1), dfs(index + 2) when the two digits form 10 to 26, and one store.
(N + 1) x O(1) + 2(N + 1) x O(1) = O(N)
At most N + 1 calls explore and each makes at most two calls, so at most 3(N + 1) calls run in all, each doing constant work outside its children.
Variable Definitions
len(s), the number of digits
Memory Architecture & Bounds
O(N): one frame per digit read, at most N + 1 deep
O(N): memo, at most one entry per index
O(1): one integer
Boundary Best / Worst Cases
: s[0] == "0" returns 0 at once
: a string of 1s and 2s, where every index branches twice
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "count how many distinct ways", "can often be split into letters in more than one way". Each digit opens a one-digit and a two-digit branch, and many split paths reach the same index: Memoization, one stored answer per index.
. The plain recursion makes about calls on a run of 1s (317,810 calls for 25 ones); with the memo at most calls run. A recursion depth of 101 frames is far below Python's default limit of 1,000.
Where the cache lives: create memo (or the functools.cache-wrapped dfs) inside numDecodings, so every call starts empty. A module-level cache keeps every earlier string's answers in memory and grows with every call.