LeetCode Decode Ways II

LeetCode Decode Ways II
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'.

```const int MOD = 1000000007;
typedef long long ll;
class Solution {
public:
int numDecodings(string s) {
if (s == "" || s[0] == '0')return 0;
s = "^" + s;
int n = s.size();
vector<ll> dp(n, 0);
dp[0] = 1;
if (s[1] == '*')dp[1] = 9;
else dp[1] = 1;
for (int i = 2; i < n; i++)
{
if (s[i] >= '1' && s[i] <= '9')
dp[i] += dp[i - 1] % MOD; // 独自解析
if ((s[i - 1] == '1' && s[i] >= '0' && s[i] <= '9') || (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6'))
dp[i] += dp[i - 2] % MOD;
if (s[i - 1] == '*'&&s[i] >= '0'&&s[i] <= '9') {
if (s[i] >= '0'&&s[i] <= '6')dp[i] += dp[i - 2] * 2 % MOD;
if (s[i] > '6')dp[i] += dp[i - 2] % MOD;
}
if (s[i] == '*') {
dp[i] += dp[i - 1] * 9 % MOD; // 独自解析
if (s[i - 1] != '*') {
if (s[i - 1] == '1')dp[i] += dp[i - 2] * 9 % MOD;
else if (s[i - 1] == '2')dp[i] += dp[i - 2] * 6 % MOD;
}
else {
dp[i] += dp[i - 2] * 15 % MOD;
}
}
dp[i] %= MOD;
}
return dp[n - 1];
}
};
```

```class Solution {
public:
int numDecodings(string s) {
if (s == "" || s[0] == '0')return 0;
s = "^" + s;
int n = s.size();
vector<ll> dp(n, 0);
dp[0] = 1;
if (s[1] == '*')dp[1] = 9;
else dp[1] = 1;
for (int i = 2; i < n; i++) {
char cur = s[i], pre = s[i - 1];
ll &curCnt = dp[i], preCnt = dp[i - 1], prePreCnt = dp[i - 2];
if (cur == '0') {
if (pre == '1'|| pre == '2')curCnt += prePreCnt % MOD;
else if (pre == '*')curCnt += prePreCnt * 2 % MOD;
else return 0;
}
else if (cur == '*') {
curCnt += preCnt * 9 % MOD;
if (pre == '1')curCnt += prePreCnt * 9 % MOD;
else if (pre == '2')curCnt += prePreCnt * 6 % MOD;
else if (pre == '*')curCnt += prePreCnt * 15 % MOD;
}
else { // ['1','9']
curCnt += preCnt % MOD;
if(pre=='1')curCnt += prePreCnt % MOD;
else if (pre == '2' && cur <= '6')curCnt += prePreCnt % MOD;
else if (pre == '*') {
if (cur <= '6')curCnt += prePreCnt * 2 % MOD;
else curCnt += prePreCnt % MOD;
}
}
curCnt %= MOD;
}
return dp[n - 1];
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.