# Decode Ways II **Difficulty:** HARD [External](https://leetcode.com/problems/decode-ways-ii) Canonical: https://scaleengineer.com/dsa/problems/decode-ways-ii **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Data structures:** String **Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe) --- ## Problem 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 <= 105` * `s[i]` is a digit or `'*'`. # Approaches ## Top-Down Dynamic Programming (Recursion with Memoization) 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. **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. **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 `StackOverflowError` for 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. ### Explanation 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: 1. **Decode `s[i]` as a single character:** This is possible if `s[i]` is not '0'. The number of ways depends on `s[i]`: 9 if it's `'*'`, 1 if it's '1'-'9'. We add this count multiplied by `solve(i+1)` to our total. 2. **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 of `s[i]` and `s[i+1]` (e.g., '1*' gives 9 ways, '**' gives 15 ways). We add this count multiplied by `solve(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. ```java 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; } } ``` ### Algorithm 1. Define a recursive function, say `solve(index)`, that returns the number of ways to decode the substring `s[index:]`. 2. The base case for the recursion is when `index` reaches the end of the string (`index == s.length()`). In this case, we have found one valid decoding, so we return 1. 3. Use a memoization array, say `memo`, to store the results of `solve(index)` to avoid recomputing for the same index. Initialize `memo` with a value indicating that the state has not been computed (e.g., -1). 4. In the `solve(index)` function, first check if `memo[index]` has been computed. If so, return the stored value. 5. Otherwise, calculate the number of ways by considering two possibilities for the current position `index`: a. **Single-digit decoding**: Consider `s[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**: If `index + 1` is within the string bounds, consider the pair `s[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 of `solve(index + 2)`. 6. Sum the ways from both possibilities (modulo `10^9 + 7`). 7. Store the result in `memo[index]` before returning. ## Bottom-Up Dynamic Programming (O(N) Space) 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. **Time:** O(N), as we iterate through the string once to fill the DP table. · **Space:** O(N) for the DP array. **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). ### Explanation 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 on `s[0]`. If `s[0]` is `'*'`, `dp[1]=9`. If `s[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]`. ```java 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]; } } ``` ### Algorithm 1. Create a DP array, `dp`, of size `n+1`, where `n` is the length of the string `s`. 2. `dp[i]` will store the number of ways to decode the prefix of `s` of length `i`. 3. Initialize the base cases: - `dp[0] = 1` (for an empty string). - `dp[1]` depends on `s[0]`: 9 if `s[0] == '*'`, 1 if `s[0]` is '1'-'9', and 0 if `s[0] == '0'`. 4. Iterate from `i = 2` to `n` to fill the `dp` array. 5. For each `i`, calculate `dp[i]` based on the number of ways to decode the last one or two characters: a. **Single-digit decoding**: Add `ways(s[i-1]) * dp[i-1]` to `dp[i]`. The number of ways is 9 for `'*'`, 1 for '1'-'9', and 0 for '0'. b. **Two-digit decoding**: Add `ways(s[i-2], s[i-1]) * dp[i-2]` to `dp[i]`. The number of ways depends on the pair of characters, as detailed in the previous approach. 6. All additions should be performed modulo `10^9 + 7`. 7. The final answer is `dp[n]`. ## Bottom-Up Dynamic Programming (O(1) Space) 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. **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. **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. ### Explanation 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. ```java 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; } } ``` ### Algorithm 1. Observe that the calculation of `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`. 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` (for `dp[i-1]`) and `prev2` (for `dp[i-2]`). 3. Initialize `prev2 = 1` (representing `dp[0]`) and `prev1` based on `s[0]` (representing `dp[1]`). 4. Iterate from `i = 2` to `n`. 5. In each iteration, calculate a `current` value (which would be `dp[i]`) using the same logic as the O(N) space approach, but with `prev1` and `prev2`. `current = (ways_one_char * prev1 + ways_two_chars * prev2) % MOD` 6. After calculating `current`, update the variables for the next iteration: `prev2` becomes `prev1`, and `prev1` becomes `current`. 7. After the loop, `prev1` will hold the final result (`dp[n]`). # Solutions ### Java ```java 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 ; } } ``` ### Python ```python 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 c ```