A message containing letters from A-Z can be encoded into numbers using the following 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 the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF" with the grouping (1 1 10 6)"KJF" with the grouping (11 10 6)Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
In addition to the mapping above, an encoded message may contain the '*' character, which can represent any digit from '1' to '9' ('0' is excluded). For example, the encoded message "1*" may represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Decoding "1*" is equivalent to decoding any of the encoded messages it can represent.
Given a string s consisting of digits and '*' characters, return the number of ways to decode it.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: s = "*" Output: 9 Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9". Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively. Hence, there are a total of 9 ways to decode "*".
Example 2:
Input: s = "1*" Output: 18 Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19". Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K"). Hence, there are a total of 9 * 2 = 18 ways to decode "1*".
Example 3:
Input: s = "2*" Output: 15 Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29". "21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way. Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".
Constraints:
1 <= s.length <= 105s[i] is a digit or '*'.Decode Ways II extends the classic decoding problem by introducing the * wildcard, which can represent digits from 1 to 9. The main challenge is counting all valid decoding combinations while handling multiple possibilities introduced by *.
A common strategy is dynamic programming. Let dp[i] represent the number of ways to decode the substring up to index i. For each position, consider both single-digit and two-digit decoding possibilities. When encountering *, calculate how many valid digits or pairs it can represent (e.g., * alone can map to 9 digits, and combinations like 1* or *2 can represent multiple valid two-digit numbers).
Because the number of combinations grows quickly, results are typically computed modulo 10^9 + 7. The optimized approach uses only the previous states instead of a full array, reducing memory usage while maintaining linear traversal.
This results in an efficient solution with O(n) time complexity while carefully accounting for all wildcard decoding cases.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with rolling states | O(n) | O(1) |
| Standard DP array | O(n) | O(n) |
CrioDo
This approach utilizes a dynamic programming (DP) technique to solve the problem. We define a DP array where dp[i] represents the number of ways to decode the substring of length i. We iterate through the string, updating the DP array based on the current character and its possible pairings with the previous character.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(n), due to the dynamic programming array used.
1def numDecodings(s: str) -> int:
2 MOD = 10**9 + 7
3 n = len(s)
4 if n == 0:
5 return 0
6
7 dp = [0] * (n + 1)
8 dp[0] = 1
9
10 if s[0] == '*':
11 dp[1] = 9
12 elif s[0] != '0':
13 dp[1] = 1
14
15 for i in range(2, n + 1):
16
17 first = s[i-1]
18 second = s[i-2]
19
20 if first == '*':
21 dp[i] = 9 * dp[i-1]
22 elif first != '0':
23 dp[i] = dp[i-1]
24
25 if second == '*':
26 if first == '*':
27 dp[i] = (dp[i] + 15 * dp[i-2]) % MOD
28 elif '0' <= first <= '6':
29 dp[i] = (dp[i] + 2 * dp[i-2]) % MOD
30 else:
31 dp[i] = (dp[i] + dp[i-2]) % MOD
32 elif second == '1':
33 if first == '*':
34 dp[i] = (dp[i] + 9 * dp[i-2]) % MOD
35 else:
36 dp[i] = (dp[i] + dp[i-2]) % MOD
37 elif second == '2':
38 if first == '*':
39 dp[i] = (dp[i] + 6 * dp[i-2]) % MOD
40 elif '0' <= first <= '6':
41 dp[i] = (dp[i] + dp[i-2]) % MOD
42
43 return dp[n] % MODThis solution introduces a dynamic programming approach. The dp[i] array stores the number of decoding ways for the substring up to the ith character. The initial state is set based on the first character, considering '.' as all digits 1-9. Each subsequent character adjusts dp[i] depending on its value and the preceding character(s), also accounting for the '*' possibilities. All computations are done modulo 10^9 + 7 to limit overflow.
This is a space-optimized version of the dynamic programming solution. Instead of using a full dp array, we keep track of only the last two states needed, thereby reducing space complexity.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), as we use only constant extra space.
1#include <string.h>
2
3#define
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, variations of decoding and dynamic programming problems appear frequently in FAANG-style interviews. Decode Ways II is considered a harder variant due to the wildcard handling and combinatorial counting.
The optimal approach uses dynamic programming to track the number of decoding ways up to each position in the string. Special care is taken to handle the '*' wildcard, which can represent digits from 1 to 9. Optimized implementations reduce space by keeping only the previous states.
The '*' character can represent any digit from 1 to 9, which introduces multiple decoding possibilities at each step. When combined with adjacent characters, it can form several valid two-digit numbers, significantly increasing the number of cases to consider.
A dynamic programming approach using variables or an array is most effective. It tracks the number of valid decodings up to each index while accounting for single-digit and two-digit possibilities involving the wildcard.
This C solution optimizes space by maintaining only two integer variables, prev and curr, to store results of the previous and current positions respectively. This replaces the need for an entire dp array, reducing space usage while maintaining the dynamic programming logic.