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 '*'.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.
This 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.
Java
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(n), due to the dynamic programming array used.
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.
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.
JavaScript
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), as we use only constant extra space.
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n), where |
| Space Optimized Dynamic Programming | Time Complexity: O(n), where |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,607 views views
Watch 9 more video solutions →Practice Decode Ways II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor