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’.

本题是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。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *