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。

完整代码如下:

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];
	}
};

本代码提交AC,用时72MS。比赛的时候dp数组用int存的,死活WA,比赛结束那一秒,改成long long之后就AC了,但是比赛已经结束了。。。

看了下TOP代码,思路比我的稍微清晰一点,原理都是一样的,重构我的代码如下:

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];

	}
};

本代码提交AC,用时105MS。

Leave a Reply

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