Leetcode 639. 解码方法 2 C++

Leetcode 639. 解码方法 2

题目

一条包含字母 A-Z 的消息通过以下的方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

除了上述的条件以外，现在加密字符串可以包含字符 ’ * ‘了，字符’ * '可以被当做1到9当中的任意一个数字。

给定一条包含数字和字符’*'的加密信息，请确定解码方法的总数。

同时，由于结果值可能会相当的大，所以你应当对109 + 7取模。（翻译者标注：此处取模主要是为了防止溢出）

测试样例

示例 1 :

输入: "*"
输出: 9
解释: 加密的信息可以被解密为: "A", "B", "C", "D", "E", "F", "G", "H", "I".

示例 2 :

输入: "1*"
输出: 9 + 9 = 18（翻译者标注：这里1*可以分解为1,* 或者当做1*来处理，所以结果是9+9=18）

说明 :

• 输入的字符串长度范围是 [1, 10⁵]。
• 输入的字符串只会包含字符 ‘*’ 和 数字’0’ - ‘9’。

题解

动态规划
令dp[i]表示从0~i解密方式
则转移方程为

• 当s[i]!=*
  • dp[i] = dp[i-1]+1+(if 如果s[i-1]s[i]<=26 +dp[i-2]+1 then +0)
• s[i]==*
  • dp[i] = dp[i-1]+9 + (if s[i-1]==1 +dp[i-2]+1 else if s[i-1]==2 +dp[i-2]+7 else +0)
    初始条件，我们需要考虑dp[0]、dp[1]
    详细过程见代码

代码

	int numDecodings(string s) {
        if(s.empty())   return 0;
        int mod = pow(10,9)+7,len=s.length();
        if(len == 1){		//只有1位时
            if(s[0] == '0') return 0;		//没有此情况
            if(s[0] == '*') return 9;		//可以将*解码为1~9，9种情况
            return 1;
        }
        vector<long> dp(len,0);
        if(s[0]=='0')   return 0;
        if(s[0]=='*')   dp[0]=9;
        else dp[0]=1;
        if(s[1]=='*'){			//考虑前两位
            dp[1] = dp[0]*9;	//两位单独解密
            if(s[0]=='1') dp[1] += 9;       //11~19
            else if(s[0]=='2')    dp[1] += 6;   //21~26，6种情况
            else if(s[0]=='*')    dp[1] += 15;  //11~19+21~26，15种情况
        }else if(s[1]=='0'){		//只有10、20两种情况
            if(s[0]=='0' || s[0]<='9' && s[0]>'2')  return 0;   
            if(s[0]=='*')   dp[1] = 2;      //10+20 两种情况
            else dp[1] = 1;			//10或20
        }else{
            dp[1] = dp[0];		//两位单独解密
            if(s[0]=='1')   dp[1]++;		//出现2位共同解码，即11~19中的1种情况
            else if(s[0]=='2' && s[1]<'7')  dp[1]++;		//出现2位共同解码，即21~26中的1种情况
            else if(s[0]=='*' && s[1]<'7')  dp[1]+=2;		//11~16中的1种情况及21~26中的1种情况，共2种情况
            else if(s[0]=='*' && s[1]>'6')  dp[1]++;   		//17~19中的1种情况
        }
        for(int i=2; i<len; i++){
            if(s[i]=='*'){
                dp[i] = (dp[i-1]*9)%mod;		//s[i]可以单独解密
                if(s[i-1]!='0'){
                    if(s[i-1]=='*') dp[i] = (dp[i]+dp[i-2]*15)%mod;		//s[i-1]和s[i]作为一个整体进行解密，且可以解密为11~19+21~26，15种情况
                    else if(s[i-1]=='1')    dp[i] = (dp[i]+dp[i-2]*9)%mod;	//s[i-1]和s[i]作为一个整体进行解密，且可以解密为11~19，9种情况
                    else if(s[i-1]=='2')    dp[i] = (dp[i]+dp[i-2]*6)%mod;	//s[i-1]和s[i]作为一个整体进行解密，且可以解密为21~26，6种情况
                } 
            }else if(s[i]=='0'){		//只能是10或20
                if(s[i-1]=='0' || s[i-1]<='9' && s[i-1]>'2')  return 0;		
                if(s[i-1]=='*') dp[i] = (dp[i-2]*2)%mod;		//s[i-1]和s[i]作为一个整体进行解密，解密为10和20，2种情况
                else    dp[i] = dp[i-2];		//s[i-1]和s[i]作为一个整体进行解密，解密为10或20，1种情况
            }else{
                dp[i] = dp[i-1];		//s[i]可以单独解密
                if(s[i-1]=='1') dp[i] = (dp[i]+dp[i-2])%mod;	//s[i-1]和s[i]作为一个整体进行解密，且可以解密为11~19+21~26中的1种情况
                else if(s[i-1]=='2' && s[i]<'7')    dp[i] = (dp[i]+dp[i-2])%mod; 	//s[i-1]和s[i]作为一个整体进行解密，且可以解密为11~16+21~26中的1种情况
                else if(s[i-1]=='*' && s[i]<'7')  dp[i] = (dp[i]+dp[i-2]*2)%mod;	//s[i-1]和s[i]作为一个整体进行解密，且可以解密为11~16中的1种情况和21~26中的1种情况，共2种情况
                else if(s[i-1]=='*' && s[i]>'6')  dp[i] = (dp[i]+dp[i-2])%mod;	//s[i-1]和s[i]作为一个整体进行解密，且可以解密为17~19中的1种情况
            }
        }
        return dp[len-1];
    }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。