Decode Ways II
HardPrompt
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'*'.
Approaches
3 approaches with complexity analysis and trade-offs.
This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for Dynamic Programming. A top-down DP approach using recursion with memoization is a natural way to solve it. We define a recursive function that computes the number of ways to decode a suffix of the string. To avoid recomputing the same subproblem, we store the results in a memoization table.
Algorithm
- Define a recursive function, say
solve(index), that returns the number of ways to decode the substrings[index:]. - The base case for the recursion is when
indexreaches the end of the string (index == s.length()). In this case, we have found one valid decoding, so we return 1. - Use a memoization array, say
memo, to store the results ofsolve(index)to avoid recomputing for the same index. Initializememowith a value indicating that the state has not been computed (e.g., -1). - In the
solve(index)function, first check ifmemo[index]has been computed. If so, return the stored value. - Otherwise, calculate the number of ways by considering two possibilities for the current position
index: a. Single-digit decoding: Considers[index]. Calculate the number of ways this single character can be decoded (1 for '1'-'9', 9 for '*', 0 for '0') and multiply it by the result of the recursive call for the rest of the string,solve(index + 1). b. Two-digit decoding: Ifindex + 1is within the string bounds, consider the pairs[index]s[index+1]. Calculate the number of ways this pair can form a valid number (10-26), handling all combinations of digits and'*', and multiply it by the result ofsolve(index + 2). - Sum the ways from both possibilities (modulo
10^9 + 7). - Store the result in
memo[index]before returning.
Walkthrough
We can define a function solve(i) which calculates the number of ways to decode the suffix of the string starting at index i. The total number of ways for solve(i) is the sum of ways from two choices:
- Decode
s[i]as a single character: This is possible ifs[i]is not '0'. The number of ways depends ons[i]: 9 if it's'*', 1 if it's '1'-'9'. We add this count multiplied bysolve(i+1)to our total. - Decode
s[i]s[i+1]as a two-digit character: This is possible if the pair forms a number between 10 and 26. The number of ways depends on the combination ofs[i]ands[i+1](e.g., '1*' gives 9 ways, '**' gives 15 ways). We add this count multiplied bysolve(i+2)to our total.
The base case is when we reach the end of the string (i == s.length()), which represents one successful decoding. We use a memo array to store the results for each index i to prevent redundant calculations.
class Solution { int MOD = 1_000_000_007; long[] memo; public int numDecodings(String s) { memo = new long[s.length()]; java.util.Arrays.fill(memo, -1); return (int) solve(s, 0); } private long solve(String s, int i) { if (i == s.length()) { return 1; } if (memo[i] != -1) { return memo[i]; } long ways = 0; char c1 = s.charAt(i); // Case 1: Decode one character if (c1 == '*') { ways = (ways + 9 * solve(s, i + 1)) % MOD; } else if (c1 != '0') { ways = (ways + solve(s, i + 1)) % MOD; } // Case 2: Decode two characters if (i + 1 < s.length()) { char c2 = s.charAt(i + 1); if (c1 == '*') { if (c2 == '*') { // ** -> 11-19, 21-26 ways = (ways + 15 * solve(s, i + 2)) % MOD; } else if (c2 >= '0' && c2 <= '6') { // *[0-6] -> 1[0-6], 2[0-6] ways = (ways + 2 * solve(s, i + 2)) % MOD; } else { // *[7-9] -> 1[7-9] ways = (ways + solve(s, i + 2)) % MOD; } } else if (c1 == '1') { if (c2 == '*') { // 1* -> 11-19 ways = (ways + 9 * solve(s, i + 2)) % MOD; } else { // 1[0-9] ways = (ways + solve(s, i + 2)) % MOD; } } else if (c1 == '2') { if (c2 == '*') { // 2* -> 21-26 ways = (ways + 6 * solve(s, i + 2)) % MOD; } else if (c2 >= '0' && c2 <= '6') { // 2[0-6] ways = (ways + solve(s, i + 2)) % MOD; } } } return memo[i] = ways; }}Complexity
Time
O(N), where N is the length of the string. Each subproblem `solve(i)` is computed only once.
Space
O(N) for the memoization table and the recursion stack.
Trade-offs
Pros
Often more intuitive to formulate as it directly follows the problem's recursive definition.
Naturally prunes the search space by only computing states reachable from the initial state.
Cons
Can lead to a
StackOverflowErrorfor very long strings due to deep recursion, although Java's default stack size is often large enough for the given constraints.Slightly higher overhead compared to the iterative bottom-up approach due to function calls.
A bottom-up dynamic programming approach is an iterative alternative to memoized recursion. It solves the problem by building up the solution from smaller subproblems. We use an array, dp, where dp[i] stores the number of ways to decode the prefix of the string of length i. We compute dp[i] based on the previously computed values dp[i-1] and dp[i-2], effectively eliminating recursion.
Algorithm
- Create a DP array,
dp, of sizen+1, wherenis the length of the strings. dp[i]will store the number of ways to decode the prefix ofsof lengthi.- Initialize the base cases:
dp[0] = 1(for an empty string).dp[1]depends ons[0]: 9 ifs[0] == '*', 1 ifs[0]is '1'-'9', and 0 ifs[0] == '0'.
- Iterate from
i = 2tonto fill thedparray. - For each
i, calculatedp[i]based on the number of ways to decode the last one or two characters: a. Single-digit decoding: Addways(s[i-1]) * dp[i-1]todp[i]. The number of ways is 9 for'*', 1 for '1'-'9', and 0 for '0'. b. Two-digit decoding: Addways(s[i-2], s[i-1]) * dp[i-2]todp[i]. The number of ways depends on the pair of characters, as detailed in the previous approach. - All additions should be performed modulo
10^9 + 7. - The final answer is
dp[n].
Walkthrough
We can build the solution iteratively. Let dp[i] be the number of ways to decode the string s of length i. We want to find dp[n].
Base Cases:
dp[0] = 1: There's one way to decode an empty string (the empty decoding).dp[1]: Depends ons[0]. Ifs[0]is'*',dp[1]=9. Ifs[0]is'0',dp[1]=0. Otherwise,dp[1]=1.
Recurrence Relation:
For i > 1, dp[i] is calculated by considering the last character s[i-1] and the last two characters s[i-2]s[i-1].
- Ways from the last single character
s[i-1]: This is(ways to decode s[i-1]) * dp[i-1]. - Ways from the last two characters
s[i-2]s[i-1]: This is(ways to decode s[i-2]s[i-1]) * dp[i-2].
dp[i] = (ways_one_char * dp[i-1] + ways_two_chars * dp[i-2]) % MOD
We iterate from i=2 to n, filling the dp table. The final answer is dp[n].
class Solution { public int numDecodings(String s) { int n = s.length(); int MOD = 1_000_000_007; long[] dp = new long[n + 1]; dp[0] = 1; if (s.charAt(0) == '0') { dp[1] = 0; } else if (s.charAt(0) == '*') { dp[1] = 9; } else { dp[1] = 1; } for (int i = 2; i <= n; i++) { char c1 = s.charAt(i - 2); char c2 = s.charAt(i - 1); // Case 1: Decode one character (c2) if (c2 == '*') { dp[i] = (9 * dp[i - 1]) % MOD; } else if (c2 != '0') { dp[i] = dp[i - 1]; } // Case 2: Decode two characters (c1c2) if (c1 == '*') { if (c2 == '*') { // ** dp[i] = (dp[i] + 15 * dp[i - 2]) % MOD; } else if (c2 >= '0' && c2 <= '6') { // *[0-6] dp[i] = (dp[i] + 2 * dp[i - 2]) % MOD; } else { // *[7-9] dp[i] = (dp[i] + dp[i - 2]) % MOD; } } else if (c1 == '1') { if (c2 == '*') { // 1* dp[i] = (dp[i] + 9 * dp[i - 2]) % MOD; } else { // 1[0-9] dp[i] = (dp[i] + dp[i - 2]) % MOD; } } else if (c1 == '2') { if (c2 == '*') { // 2* dp[i] = (dp[i] + 6 * dp[i - 2]) % MOD; } else if (c2 >= '0' && c2 <= '6') { // 2[0-6] dp[i] = (dp[i] + dp[i - 2]) % MOD; } } } return (int) dp[n]; }}Complexity
Time
O(N), as we iterate through the string once to fill the DP table.
Space
O(N) for the DP array.
Trade-offs
Pros
Avoids recursion and the risk of stack overflow.
Generally more efficient than the top-down approach due to the absence of function call overhead.
The logic is straightforward to follow from base cases to the final solution.
Cons
Uses O(N) space, which might be substantial for very large N (up to 10^5 in this problem).
This is the most efficient approach, optimizing the space complexity of the bottom-up DP solution. Since the computation of the number of decodings at position i only depends on the results at i-1 and i-2, we don't need to store the entire DP table. We can keep track of only the last two values, reducing the space complexity to constant.
Algorithm
- Observe that the calculation of
dp[i]only depends ondp[i-1]anddp[i-2]. - Instead of a full DP array, we can use two variables to store the results for the previous two states. Let's call them
prev1(fordp[i-1]) andprev2(fordp[i-2]). - Initialize
prev2 = 1(representingdp[0]) andprev1based ons[0](representingdp[1]). - Iterate from
i = 2ton. - In each iteration, calculate a
currentvalue (which would bedp[i]) using the same logic as the O(N) space approach, but withprev1andprev2.current = (ways_one_char * prev1 + ways_two_chars * prev2) % MOD - After calculating
current, update the variables for the next iteration:prev2becomesprev1, andprev1becomescurrent. - After the loop,
prev1will hold the final result (dp[n]).
Walkthrough
We can optimize the space of the bottom-up DP approach. Notice that dp[i] only depends on dp[i-1] and dp[i-2]. This means we only need to store the last two computed values to find the next one. We can use two variables, say prev2 to store the value for dp[i-2] and prev1 for dp[i-1].
We initialize prev2 = 1 (for the empty prefix) and prev1 based on the first character s[0]. Then, we iterate from the third character (i=2) to the end of the string. In each step, we calculate current (the equivalent of dp[i]) using prev1 and prev2. After the calculation, we update prev2 = prev1 and prev1 = current to prepare for the next iteration. The final answer is the value of prev1 after the loop finishes.
class Solution { public int numDecodings(String s) { int n = s.length(); int MOD = 1_000_000_007; long prev2 = 1; // Corresponds to dp[i-2] long prev1; // Corresponds to dp[i-1] // Base case for the first character (i=1) if (s.charAt(0) == '0') { prev1 = 0; } else if (s.charAt(0) == '*') { prev1 = 9; } else { prev1 = 1; } for (int i = 2; i <= n; i++) { long current = 0; char c1 = s.charAt(i - 2); char c2 = s.charAt(i - 1); // Case 1: Decode one character (c2) if (c2 == '*') { current = (9 * prev1) % MOD; } else if (c2 != '0') { current = prev1; } // Case 2: Decode two characters (c1c2) if (c1 == '*') { if (c2 == '*') { // ** current = (current + 15 * prev2) % MOD; } else if (c2 >= '0' && c2 <= '6') { // *[0-6] current = (current + 2 * prev2) % MOD; } else { // *[7-9] current = (current + prev2) % MOD; } } else if (c1 == '1') { if (c2 == '*') { // 1* current = (current + 9 * prev2) % MOD; } else { // 1[0-9] current = (current + prev2) % MOD; } } else if (c1 == '2') { if (c2 == '*') { // 2* current = (current + 6 * prev2) % MOD; } else if (c2 >= '0' && c2 <= '6') { // 2[0-6] current = (current + prev2) % MOD; } } prev2 = prev1; prev1 = current; } return (int) prev1; }}Complexity
Time
O(N), as it involves a single pass through the input string.
Space
O(1), as we only use a few variables to store previous results, regardless of the input string's length.
Trade-offs
Pros
Extremely space-efficient, using only a constant amount of extra space.
Maintains the optimal O(N) time complexity.
It's the most performant solution for this problem.
Cons
The logic of updating variables (
prev1,prev2) can be slightly more error-prone than using a DP array with explicit indices.
Solutions
Solution
class Solution { private static final int MOD = 1000000007 ; public int numDecodings ( String s ) { int n = s . length (); char [] cs = s . toCharArray (); // dp[i - 2], dp[i - 1], dp[i] long a = 0 , b = 1 , c = 0 ; for ( int i = 1 ; i <= n ; i ++) { // 1 digit if ( cs [ i - 1 ] == '*' ) { c = 9 * b % MOD ; } else if ( cs [ i - 1 ] != '0' ) { c = b ; } else { c = 0 ; } // 2 digits if ( i > 1 ) { if ( cs [ i - 2 ] == '*' && cs [ i - 1 ] == '*' ) { c = ( c + 15 * a ) % MOD ; } else if ( cs [ i - 2 ] == '*' ) { if ( cs [ i - 1 ] > '6' ) { c = ( c + a ) % MOD ; } else { c = ( c + 2 * a ) % MOD ; } } else if ( cs [ i - 1 ] == '*' ) { if ( cs [ i - 2 ] == '1' ) { c = ( c + 9 * a ) % MOD ; } else if ( cs [ i - 2 ] == '2' ) { c = ( c + 6 * a ) % MOD ; } } else if ( cs [ i - 2 ] != '0' && ( cs [ i - 2 ] - '0' ) * 10 + cs [ i - 1 ] - '0' <= 26 ) { c = ( c + a ) % MOD ; } } a = b ; b = c ; } return ( int ) c ; } }class Solution : def numDecodings ( self , s : str ) -> int : mod = int ( 1e9 + 7 ) n = len ( s ) # dp[i - 2], dp[i - 1], dp[i] a , b , c = 0 , 1 , 0 for i in range ( 1 , n + 1 ): # 1 digit if s [ i - 1 ] == "*" : c = 9 * b % mod elif s [ i - 1 ] != "0" : c = b else : c = 0 # 2 digits if i > 1 : if s [ i - 2 ] == "*" and s [ i - 1 ] == "*" : c = ( c + 15 * a ) % mod elif s [ i - 2 ] == "*" : if s [ i - 1 ] > "6" : c = ( c + a ) % mod else : c = ( c + 2 * a ) % mod elif s [ i - 1 ] == "*" : if s [ i - 2 ] == "1" : c = ( c + 9 * a ) % mod elif s [ i - 2 ] == "2" : c = ( c + 6 * a ) % mod elif ( s [ i - 2 ] != "0" and ( ord ( s [ i - 2 ]) - ord ( "0" )) * 10 + ord ( s [ i - 1 ]) - ord ( "0" ) <= 26 ): c = ( c + a ) % mod a , b = b , c return cVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.