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).The key challenge in Decode Ways is determining how many valid ways a numeric string can be interpreted as letters where 1 -> A through 26 -> Z. Since each digit can form a decoding either alone or combined with the next digit, the problem naturally fits a dynamic programming pattern.
Think of the problem as counting the number of ways to decode up to each index in the string. For every position, you check whether the current digit forms a valid single-digit mapping and whether the current and previous digits together form a valid two-digit mapping (between 10 and 26). Using a DP array (or optimized variables), you accumulate the number of valid decodings.
This approach ensures that each character is processed once while handling tricky edge cases such as 0 values that cannot be decoded alone. The optimized solution runs in O(n) time with O(1) or O(n) space depending on implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (count ways using previous states) | O(n) | O(n) or O(1) with space optimization |
NeetCode
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.
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.
1var numDecodings = function(s) {
2 if (!s || s[0] === '0') return 0;
3 let n =
JavaScript's solution leverages arrays, slice operations, and parseInt for character manipulation, considering single and two-character possibilities sequentially.
It manages an array similarly to establish counts of valid decodings observed at any index level.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Decode Ways is a popular medium-level dynamic programming problem often asked in technical interviews, including FAANG-style interviews, to test DP thinking and edge case handling.
The optimal approach uses dynamic programming. At each position in the string, you count valid decodings by considering both single-digit and two-digit mappings, building results from previously computed states.
Dynamic programming works well because the number of decodings up to a position depends on earlier results. By storing intermediate counts, you avoid recomputation and process the string efficiently in linear time.
Special attention is needed for the digit '0', since it cannot be decoded alone. Only combinations like 10 or 20 are valid, so inputs with leading zeros or invalid pairs must be handled carefully.
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.