Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/639.html
639. Decode Ways II (Hard)
A message containing letters from A-Z is being encoded to numbers using the following mapping way:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:
Input: "*" Output: 9 Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
Example 2:
Input: "1*" Output: 9 + 9 = 18
Note:
- The length of the input string will fit in range [1, 105].
- The input string will only contain the character '*' and digits '0' - '9'.
Related Topics:
Dynamic Programming
Similar Questions:
Solution 1. DP
// OJ: https://leetcode.com/problems/decode-ways-ii/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/decode-ways-ii/solution/
class Solution {
void add(long &a, long b) { a = (a + b) % ((int)1e9+7); }
public:
int numDecodings(string s) {
long prev1 = s[0] == '*' ? 9 : (s[0] != '0'), prev2 = 1;
for (int i = 1; i < s.size(); ++i) {
long cur = 0;
if (s[i] == '*') {
cur = 9 * prev1;
if (s[i - 1] == '1') add(cur, 9 * prev2);
else if (s[i - 1] == '2') add(cur, 6 * prev2);
else if (s[i - 1] == '*') add(cur, 15 * prev2);
} else {
cur = s[i] != '0' ? prev1 : 0;
if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) add(cur, prev2);
else if (s[i - 1] == '*') add(cur, (s[i] <= '6' ? 2 : 1) * prev2);
}
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};
Java
-
class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0) return 0; final int MODULO = 1000000007; int length = s.length(); long[] dp = new long[length + 1]; dp[length] = 1; dp[length - 1] = s.charAt(length - 1) == '0' ? 0 : s.charAt(length - 1) == '*' ? 9 : 1; for (int i = length - 2; i >= 0; i--) { if (s.charAt(i) == '0') dp[i] = 0; else { char c1 = s.charAt(i), c2 = s.charAt(i + 1); if (c1 == '*' && c2 == '*') { int twos = 0; for (int j = 1; j <= 9; j++) { for (int k = 1; k <= 9; k++) { int num = j * 10 + k; if (num <= 26) twos++; } } dp[i] = 9 * dp[i + 1] + twos * dp[i + 2]; } else if (c1 == '*') { int twos = 0; for (int num = 10 + c2 - '0'; num < 100; num += 10) { if (num <= 26) twos++; } dp[i] = 9 * dp[i + 1] + twos * dp[i + 2]; } else if (c2 == '*') { int twos = 0; int low = (c1 - '0') * 10 + 1, high = (c1 - '0') * 10 + 9; for (int num = low; num <= high; num++) { if (num <= 26) twos++; } dp[i] = dp[i + 1] + twos * dp[i + 2]; } else { int num = Integer.parseInt(s.substring(i, i + 2)); dp[i] = num <= 26 ? dp[i + 1] + dp[i + 2] : dp[i + 1]; } } dp[i] %= MODULO; } return (int) dp[0]; } } -
// OJ: https://leetcode.com/problems/decode-ways-ii/ // Time: O(N) // Space: O(1) // Ref: https://leetcode.com/problems/decode-ways-ii/solution/ class Solution { void add(long &a, long b) { a = (a + b) % ((int)1e9+7); } public: int numDecodings(string s) { long prev1 = s[0] == '*' ? 9 : (s[0] != '0'), prev2 = 1; for (int i = 1; i < s.size(); ++i) { long cur = 0; if (s[i] == '*') { cur = 9 * prev1; if (s[i - 1] == '1') add(cur, 9 * prev2); else if (s[i - 1] == '2') add(cur, 6 * prev2); else if (s[i - 1] == '*') add(cur, 15 * prev2); } else { cur = s[i] != '0' ? prev1 : 0; if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) add(cur, prev2); else if (s[i - 1] == '*') add(cur, (s[i] <= '6' ? 2 : 1) * prev2); } prev2 = prev1; prev1 = cur; } return prev1; } }; -
''' >>> 1e9 1000000000.0 >>> int(1e9 + 7) 1000000007 1e9 is a method of writing the number 1,000,000,000 in scientific notation, and is short for 1*(10^9)''' 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 ############ # ref: https://leetcode.com/problems/decode-ways-ii/discuss/105262/Python-6-lines-DP-solution one = {str(i): 1 for i in range(1, 10)} one.update({'*': 9, '0': 0}) two = {str(i): 1 for i in range(10, 27)} two.update({'*' + str(i): 2 if i <= 6 else 1 for i in range(10)}) two.update({'1*': 9, '2*': 6, '**': 15}) class Solution: def numDecodings(self, s): dp = (1, one.get(s[:1], 0)) for i in range(1, len(s)): dp = (dp[1], (one.get(s[i]) * dp[1] + two.get(s[i - 1: i + 1], 0) * dp[0]) % 1000000007) return dp[-1]