Decode Ways
Problem
Given a string s containing only digits, return the number of ways to decode it according to the mapping 'A'->1, 'B'->2, ..., 'Z'->26.
- 1 ≤ s.length ≤ 100
- s contains only digits and may contain leading zeros
Example
s = "226"3The string "226" can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). The algorithm uses recursion with memoization to count all valid decoding paths. Starting at index 0, it explores decoding one digit ('2') and then two digits ('22') if valid. It sums the counts from these recursive calls, caching results to avoid redundant computations. The critical moment is recognizing that '0' cannot be decoded alone, so paths starting with '0' return 0 immediately, pruning invalid branches.
Approach
Straightforward Solution
A brute-force recursive approach tries all possible decoding splits without caching, leading to exponential time due to overlapping subproblems and repeated computations.
Core Observation
Each position in the string can be decoded either as a single digit (if not '0') or as a valid two-digit number between 10 and 26. The total decoding ways from a position equals the sum of decoding ways from the next position and, if valid, from the position after next.
Path to Optimal
The key recognition signals are 'count number of ways', 'string of digits', and 'mapping 1 to 26'. These indicate Dynamic Programming because the problem breaks down into overlapping subproblems where the solution at index i depends on solutions at i+1 and i+2. Memoization caches results to avoid recomputation, reducing exponential recursion to linear time.
Optimal Approach
Use a top-down recursive function with memoization. The function dp(i) returns the number of decoding ways starting at index i. If s[i] is '0', return 0 immediately. Otherwise, sum dp(i+1) and dp(i+2) if the two-digit number s[i:i+2] is valid (<= 26). Store results in a memo dictionary keyed by index to ensure each subproblem is solved once. Return dp(0) as the final answer.
Time
O(n)
Each index in the string is computed once and stored in the memo dictionary. Each recursive call does O(1) work aside from recursive calls, resulting in linear time relative to the string length.
Space
O(n)
The memo dictionary stores results for each index, requiring O(n) auxiliary space. The recursion stack depth is at most n, also contributing O(n) space.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When counting ways to decode or partition sequences with overlapping subproblems, use recursion with memoization to cache intermediate results, transforming exponential brute-force into efficient linear-time solutions.
Solution
| 1 | class Solution:
|
| 2 | def numDecodings(self, s: str) -> int:
|
| 3 | memo = { len(s): 1 }
|
| 4 |
|
| 5 | def dp(i):
|
| 6 | if i in memo:
|
| 7 | return memo[i]
|
| 8 | if s[i] == "0":
|
| 9 | return 0
|
| 10 |
|
| 11 | res = dp(i + 1)
|
| 12 | if (i + 1 < len(s) and (s[i] == "1" or
|
| 13 | (s[i] == "2" and s[i + 1] in "0123456"))):
|
| 14 | res += dp(i + 2)
|
| 15 |
|
| 16 | memo[i] = res
|
| 17 | return res
|
| 18 |
|
| 19 | return dp(0) |
Step-by-Step Solution
Initialize Memoization Cache with Base Case
| 3 | memo = { len(s): 1 }
|
Objective
To set up a memo dictionary with a base case indicating that decoding beyond the last character counts as one valid way.
Key Insight
Initializing memo with the base case at index len(s) = 1 represents the empty substring after the end of the string, which counts as one valid decoding path. This base case anchors the recursion and allows dp(i) to return 1 when it reaches the end, enabling correct accumulation of decoding counts.
Interview Quick-Check
Core Logic
The memo dictionary caches results for each index, with the base case memo[len(s)] = 1 representing a successful decoding path beyond the string.
State & Boundaries
The base case ensures recursion terminates correctly when the index reaches the string length.
Recursively Compute Decoding Ways with Memoization
| 5 | def dp(i):
|
| 6 | if i in memo:
|
| 7 | return memo[i]
|
| 8 | if s[i] == "0":
|
| 9 | return 0
|
| 11 | res = dp(i + 1)
|
| 12 | if (i + 1 < len(s) and (s[i] == "1" or
|
| 13 | (s[i] == "2" and s[i + 1] in "0123456"))):
|
| 14 | res += dp(i + 2)
|
| 16 | memo[i] = res
|
| 17 | return res
|
Objective
To recursively calculate the number of decoding ways starting at index i, using memoization to avoid redundant computations.
Key Insight
The recursive function dp(i) returns 0 if the current character is '0' since '0' cannot be decoded alone. Otherwise, it counts ways by decoding one digit (dp(i+1)) and, if valid, two digits (dp(i+2)). Memoization stores results for each index to prevent exponential recomputation. This approach exploits the problem's optimal substructure and overlapping subproblems, enabling efficient linear-time computation.
Interview Quick-Check
Core Logic
The recursion explores decoding one digit and two digits when valid, summing their counts to get total decoding ways from index i.
State & Boundaries
Returning 0 immediately for '0' digits prunes invalid decoding paths.
Common Pitfalls & Bugs
Forgetting to check if the two-digit number is <= 26 or mishandling '0' digits leads to incorrect counts.
Complexity
Memoization ensures each index is computed once, reducing time complexity from exponential to linear.
Return Total Decoding Ways from Start of String
| 19 | return dp(0) |
Objective
To initiate the recursive decoding count from index 0 and return the total number of valid decoding ways for the entire string.
Key Insight
Starting the recursion at index 0 triggers the full exploration of all valid decoding paths. The memoized recursion efficiently aggregates counts from all valid splits, returning the final total number of ways to decode the input string.
Interview Quick-Check
Core Logic
Calling dp(0) starts the recursive process that computes the total decoding ways for the entire string.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if i in memo:Return cached result if index i has been computed before.
Memoization lookup prevents redundant recursive calls, reducing exponential time complexity to linear by reusing previously computed results.
return memo[i]Return memoized decoding count for index i.
Returning the cached value immediately ensures efficient reuse of computed subproblem results.
if s[i] == "0":Return 0 if current character is '0', as it cannot be decoded alone.
This early pruning is critical to correctness, as '0' digits do not map to any letter and invalidate decoding paths starting here.
if (i + 1 < len(s) and (s[i] == "1" orCheck if two-digit decoding is possible and valid (<= 26).
This conditional ensures two-digit decoding is only counted when the substring forms a valid letter mapping, preventing invalid counts.
memo[i] = resCache the total decoding ways for index i.
Memoizing the result for index i prevents recomputation of this subproblem, enabling efficient linear-time complexity.
memo = { len(s): 1 }Initialize memo dictionary with base case for recursion termination.
Setting memo[len(s)] = 1 represents one valid decoding path beyond the end of the string, anchoring the recursion and enabling correct accumulation of decoding counts.
return 0Return 0 for invalid decoding paths starting with '0'.
Returning zero here prevents counting invalid decoding sequences, ensuring only valid paths contribute to the total.
res = dp(i + 1)Recursively count decoding ways by decoding one digit.
Decoding a single digit advances the index by one, exploring all valid single-digit decoding paths.
(s[i] == "2" and s[i + 1] in "0123456"))):Continue condition for two-digit decoding validity.
The compound condition correctly handles the range of valid two-digit numbers (10 to 26) by checking the first digit and the second digit's allowed values.
res += dp(i + 2)Add decoding ways from decoding two digits.
Including dp(i+2) accounts for all valid decoding paths that consume two digits at once, ensuring completeness of the count.
return resReturn the cached total decoding ways for index i.
Returning the memoized result completes the recursive call, propagating the count up the call stack.
def dp(i):Define recursive function dp to compute decoding ways starting at index i.
Encapsulating the recursive logic in dp(i) allows memoization of subproblems and cleanly expresses the problem's optimal substructure.
return dp(0)Return the total number of decoding ways starting from index 0.
This initiates the recursive decoding count for the entire string, producing the final answer.
Test Your Understanding
Why must the algorithm return 0 immediately when encountering a '0' digit at the current index?
Because '0' cannot be decoded alone into any letter, any decoding path starting with '0' is invalid and contributes zero ways, so returning 0 prunes these invalid branches and ensures correctness.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Decode Ways from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Decode Ways drill