LeetCode 91&639 题解

LeetCode 91

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty()) return 0;
        vector<int> dp(s.size()+1, 0);
        if(s[0]!='0')
            dp[0] = 1;
        else
            return 0;
        dp[1] = 1;
        int tnum;
        for(int i=2;i<s.size()+1;i++){
            tnum = str2num(s[i-2], s[i-1]);
            if(tnum==10 || tnum==20) dp[i] = dp[i-2];
            else  if(tnum%10==0) return 0;
            else if((tnum>=11 && tnum<=19)||(tnum>=21 && tnum<=26)) dp[i] = dp[i-2]+dp[i-1];
            else dp[i] =dp[i-1];
            // printf("%d %d %d\n", i, dp[i], tnum);
        }
        return dp[s.size()];
    }
    int str2num(char a, char b){
        return (a-'0')*10+b-'0';
    }
};

此题使用动态规划求解。考虑当前位置与上一个位置组合形成数字的100种情形并分别进行处理即可得到答案。下面叙述中，tnum表示s[i-1]和s[i]组合成的数字。在0<=tnum<=19 || 21<=tnum<=26时，两者组合起来解释，此种情形下，其解码方式有dp[i-2]种；两者分开解释，其解码方式有dp[i-1]种。而当tnum=10 || tnum=20时，两者只能组合解释，有dp[i-2]种解释。在tnum为10的倍数且不等于10 20时，无法解释，直接返回0。而在其他情况下，两个数字智能分开解释，故解码方式为dp[i-1]。

最开始求解这道题时，被这么多的状态和情形搞蒙了，无法对应起来。而将其映射为数字之后，处理起来就方便很多了。递推关系式第一次也没弄明白。加油！

639. Decode Ways II

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty()) return 0;
        vector<long long> dp(s.size()+1, 0);
        if(s[0]=='0')
            return 0;
        else if(s[0]=='*')
            dp[1] = 9;
        else
            dp[1] = 1;
        dp[0] = 1;
        int tnum;
        char pre, cur;
        const int HI = 1e9+7;
        for(int i=2;i<s.size()+1;i++){
           if(s[i-1]!='*' && s[i-2]!='*') {
            tnum = str2num(s[i-2], s[i-1]);
            if(tnum==10 || tnum==20) dp[i] = dp[i-2];
            else  if(tnum%10==0) return 0;
            else if((tnum>=11 && tnum<=19)||(tnum>=21 && tnum<=26)) dp[i] = (dp[i-2]+dp[i-1])% HI;
            else dp[i] =dp[i-1];
            // printf("%d %d %d\n", i, dp[i], tnum);
           }
            else{
                pre = s[i-2]; cur = s[i-1];
                if(cur=='*' && pre!='*'){
                    if(pre =='1') dp[i] = ((dp[i-1]+dp[i-2])*9) % HI;
                    else if(pre == '2') dp[i] = (dp[i-1]*9+dp[i-2]*6) % HI;
                    else dp[i] = (dp[i-1]*9) % HI;
                }
                else if(cur!='*' && pre=='*'){
                    if(cur =='0') dp[i] = (dp[i-2]*2) % HI;
                    else if(cur>='1'&&cur<='6') dp[i] = (dp[i-1]+dp[i-2]*2) % HI;
                    else dp[i] = (dp[i-1]+dp[i-2]) % HI;
                }
                else
                    dp[i] = (dp[i-1]*9+dp[i-2]*15) % HI;
            }
            // printf("%d ", dp[i]);
        }
        return (int)dp[s.size()];
    }
    int str2num(char a, char b){
        return (a-'0')*10+b-'0';
    }
};

需要处理21种情况。