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:

1. The length of the input string will fit in range [1, 105].
2. 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 == '*' ? 9 : (s != '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;
}
}