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' -> 26Beyond 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 = 18Note:
- The length of the input string will fit in range [1, 105].
- The input string will only contain the character ‘*’ and digits ‘0’ – ‘9’.
本题是LeetCode Decode Ways的升级版本，引入了一个星号’*’，可以表示’1′-‘9’这9个数字。给定一个加密的字符串，问有多少种解密方法。 这个题说难也难，说简单也简单，我居然跪在了int上，把dp数组由int改为long long就AC了！ 和前一题的思路差不多，对于每个字符，都有两种可能的选择，要么该字符单独解码，要么和前一个字符组合起来解码。 设dp[i]表示前i个字符总的解密数。 对于当前字符是数字，前一个字符也是数字的情况，和前一题的思路完全一样，如果是’1’-‘9’，则可以自行解码，dp[i]+=dp[i-1]；如果前一个字符和当前字符组合的数字范围在[10,26]，可以和前一个字符组合解码，dp[i]+=dp[i-2]。 如果当前字符是数字，但前一个字符是*。如果要和前一个字符组合，当前字符如果在[‘0′,’6’]，则前一个*可以取’1’或者’2’，所以dp[i]+=dp[i-2]*2；如果当前字符是[‘7′,’9’]，则前一个*只能取’1’，所以dp[i]+=dp[i-2]。 对于*需要特殊处理。如果当前字符是*，前一个字符不是*，要和前一个字符组合，则如果前一个是’1’，则当前*可以取[‘0′,’9’]，所以dp[i]+=dp[i-2]*9；如果前一个是’2’，则当前*可以取[‘0′,’6’]，所以dp[i]+=dp[i-2]*6。其他情况都不能组合。 如果当前字符和前一个字符都是*的情况，要组合，则**的情况只有15种，注意不是26种，因为要去掉那些个位数和包含0的十位数的情况，剩下就只有15种了。所以dp[i]+=dp[i-2]*15。 完整代码如下： [cpp] 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]; } }; [/cpp] 本代码提交AC，用时72MS。比赛的时候dp数组用int存的，死活WA，比赛结束那一秒，改成long long之后就AC了，但是比赛已经结束了。。。 看了下TOP代码，思路比我的稍微清晰一点，原理都是一样的，重构我的代码如下： [cpp] 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]; } }; [/cpp] 本代码提交AC，用时105MS。]]>