You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:
"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'
However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").
For example, "11106" can be decoded into:
"AAJF" with the grouping (1, 1, 10, 6)"KJF" with the grouping (11, 10, 6)(1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).Note: there may be strings that are impossible to decode.
Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: s = "12"
Output: 2
Explanation:
"12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation:
"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06"
Output: 0
Explanation:
"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.
Constraints:
1 <= s.length <= 100s contains only digits and may contain leading zero(s).Problem Overview: You receive a string of digits where 1-26 map to letters A-Z. The task is to count how many valid ways the string can be decoded. A single digit may form a letter (1 → A) and certain pairs can form another (10 → J, 26 → Z). Invalid patterns like leading 0 or 30 must be ignored.
Approach 1: Recursive Exploration (Exponential Time)
Start at index 0 and recursively try decoding one digit or two digits if the pair forms a number between 10 and 26. Each recursive call advances the pointer and counts valid decoding paths until the end of the string. This brute-force tree explores all combinations of splits. Time complexity is O(2^n) in the worst case because each position can branch into two choices. Space complexity is O(n) due to recursion depth. This approach clarifies the structure of the problem but quickly becomes too slow for longer strings.
Approach 2: Dynamic Programming (O(n) time, O(n) space)
Dynamic programming removes repeated work from recursion. Create a dp array where dp[i] represents the number of ways to decode the prefix ending at index i. For each position, check two possibilities: decoding the current digit alone (valid if it's not 0) and decoding the last two digits together (valid if the number is between 10 and 26). Update dp[i] by adding contributions from dp[i-1] and dp[i-2]. The algorithm scans the string once, making it O(n) time with O(n) space. This is the standard solution using dynamic programming on a string.
Approach 3: Optimized Space Dynamic Programming (O(n) time, O(1) space)
The DP transition only depends on the previous two states: dp[i-1] and dp[i-2]. Instead of storing the entire array, keep two variables representing those values and update them while iterating through the string. At each step, compute the current count based on valid single-digit and two-digit decodings. This reduces memory usage to constant space while preserving the same O(n) time complexity. The technique is a common optimization pattern in dynamic programming when only a small window of previous states is required.
Recommended for interviews: The optimized dynamic programming approach is the expected answer. Interviewers want to see that you recognize overlapping subproblems, build a recurrence relation, and then reduce the DP state to constant space. Starting with the recursive idea shows understanding of the problem structure, but implementing the O(n) DP demonstrates strong problem-solving skills.
The dynamic programming approach leverages the fact that a problem can be broken into subproblems. Here, we use an array dp where dp[i] represents the number of ways to decode the substring s[0..i-1].
We iterate through the string and update the dp array based on the valid single and two-digit mappings.
In this C solution, we use an integer array dp to store the number of ways to decode the string up to each character.
We initialize dp[0] = 1 as there's one way to decode an empty string, and dp[1] = 1 because there's one way to decode a valid single character (assuming it's not '0'). We then loop through the string starting from the second character, calculating the number of ways to decode it based on one-digit and two-digit combinations.
Time Complexity: O(n), where n is the length of the input string. This is because we iterate over each character once.
Space Complexity: O(n), as we use an additional array of size n for storing our results for subproblems.
Instead of using an entire array to store all previous results, this approach keeps track of only the last two computations (since we only ever need the last two values for our dp computations).
Thus, we use two variables to hold these values and update them as needed to keep our space usage minimal.
This C solution reduces space complexity by using two variables - prev1 and prev2 to keep track of decodings without maintaining a full dp array.
These variables capture prior computations needed for the current index advance.
Time Complexity: O(n), since each character in the string is touched once.
Space Complexity: O(1), because only two variables are used to maintain state.
We define f[i] to represent the number of decoding methods for the first i characters of the string. Initially, f[0]=1, and the rest f[i]=0.
Consider how f[i] transitions.
ith character (i.e., s[i-1]) forms a code on its own, it corresponds to one decoding method, i.e., f[i]=f[i-1]. The premise is s[i-1] neq 0.i-1th character and the ith character is within the range [1,26], then they can be treated as a whole, corresponding to one decoding method, i.e., f[i] = f[i] + f[i-2]. The premise is s[i-2] neq 0, and s[i-2]s[i-1] is within the range [1,26].The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: Space Complexity: |
| Optimized Space Dynamic Programming Approach | Time Complexity: Space Complexity: |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Exploration | O(2^n) | O(n) | Conceptual understanding of all decoding combinations |
| Dynamic Programming (DP Array) | O(n) | O(n) | General solution when clarity is preferred over memory optimization |
| Optimized Space DP | O(n) | O(1) | Interview-preferred solution when memory efficiency matters |
Decode Ways - Dynamic Programming - Leetcode 91 - Python • NeetCode • 284,632 views views
Watch 9 more video solutions →Practice Decode Ways with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor