算法
动态规划 $O(n)$
与Decode Ways
类似,我们可以将'*'
的情况单独考虑。
- 如果当前字符是
'*'
,那么可以直接加上dp[i - 1] * 9
,接下来考虑两字符组合的情况,分别讨论1, 2, *
的情况就可以了。 - 如果当前字符不是
'*'
, 如果它不是'0'
的话那么可以直接加上dp[i - 1]
,接下来考虑两字符组合的情况,如果前一个字符是'1'
或者'2'
,那么和Decode Ways
是一样的,如果是'*'
的话,再看当前字符是不是小于或等于'6'
。
C++ 代码
class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0') return 0;
int n = s.length();
vector<long long> dp(n + 1);
dp[0] = 1;
dp[1] = s[0] == '*' ? 9 : 1;
int p = 1e9 + 7;
for (int i = 2; i <= n; i ++ )
{
if (s[i - 1] == '*')
{
dp[i] = (dp[i] + dp[i - 1] * 9) % p;
if (s[i - 2] == '1')
dp[i] = (dp[i] + dp[i - 2] * 9) % p;
else if (s[i - 2] == '2')
dp[i] = (dp[i] + dp[i - 2] * 6) % p;
else if (s[i - 2] == '*')
dp[i] = (dp[i] + dp[i - 2] * 15) % p;
}
else
{
if (s[i - 1] != '0') dp[i] = (dp[i] + dp[i - 1]) % p;
if (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '6')
dp[i] = (dp[i] + dp[i - 2]) % p;
else if (s[i - 2] == '*')
{
if (s[i - 1] <= '6') dp[i] = (dp[i] + dp[i - 2] * 2) % p;
else dp[i] = (dp[i] + dp[i - 2]) % p;
}
}
}
return dp[n];
}
};