leetcdode639

1.重复计算太多pass

class Solution {
public:
    int numDecodings(string s) {
        return (int)_numDecodings(s,0);
    }
    long long _numDecodings(string s,int i) {
        if(i>=s.size()){
            return 1;
        }
        //为0则此分支不合理返回0
        if(s[i]=='0'){
            return 0;
        }
        //当前步长为1
        long long ret1=s[i]=='*'?9:1;
        ret1*=_numDecodings(s,i+1);
        //当前步长为2
        long long ret2=0;
        if(i+1<s.size()&&s[i]=='*'){
            if(s[i+1]=='*'){
                //9+6=15
                ret2+=15;
            }else if(s[i+1]>='0'&&s[i+1]<='6'){
                ret2+=2;
            }else{
                ret2+=1;
            }
            
        }else if(i+1<s.size()&&(s[i]=='1'||s[i]=='2')){
            if(s[i+1]=='*'){
                if(s[i]=='1'){
                    ret2+=9;
                }else{
                    ret2+=6;
                }
            }else if(s[i]=='1'||(s[i]=='2'&&s[i+1]<'7')){
                ret2+=1;
            }
        }
        ret2*=ret2==0?0:_numDecodings(s,i+2);
        return (ret1+ret2)%1000000007;
    }
};

 2.又超时了

class Solution {
public:
    int numDecodings(string s) {
        int num1 = 0, num2 = 1, num3 = 0;
        cout<<_numDecodings1(s, 0)<<endl;
        cout<<_numDecodings2(s, 0)<<endl;
        for(int i=1;i<=s.size();i++){
            num3=(long long)num2 * _numDecodings1(s,i-1)%1000000007;
            if (i > 1) {
                num3 = (num3 + (long long)num1 * _numDecodings2(s, i-2)) % 1000000007;
            }
            num1 = num2;
            num2 = num3;
        }
        return num3;
    }
    int _numDecodings1(string s,int i){
        //为0则此分支不合理返回0
        if(s[i]=='0'){
            return 0;
        }
        return s[i]=='*'?9:1;
    }
    int _numDecodings2(string s,int i){
        if(s[i]=='0'){
            return 0;
        }
        //当前步长为2
        if(i+1<s.size()&&s[i]=='*'){
            if(s[i+1]=='*'){
                //9+6=15
                return 15;
            }else if(s[i+1]>='0'&&s[i+1]<='6'){
                return 2;
            }else{
                return 1;
            }
            
        }else if(i+1<s.size()&&(s[i]=='1'||s[i]=='2')){
            if(s[i+1]=='*'){
                if(s[i]=='1'){
                    return 9;
                }else{
                    return 6;
                }
            }else if(s[i]=='1'||(s[i]=='2'&&s[i+1]<'7')){
                return 1;
            }else{
                return 0;
            }
        }else{
            return 0;
        }
    }
};

 3.值传递改成传递引用通过

class Solution {
public:
    int numDecodings(string s) {
        int num1 = 0, num2 = 1, num3 = 0;
        //cout<<_numDecodings1(s, 0)<<endl;
        //cout<<_numDecodings2(s, 0)<<endl;
        for(int i=1;i<=s.size();i++){
            num3=(long long)num2 * _numDecodings1(s,i-1)%1000000007;
            if (i > 1) {
                num3 = (num3 + (long long)num1 * _numDecodings2(s, i-2)) % 1000000007;
            }
            num1 = num2;
            num2 = num3;
        }
        return num3;
    }
    int _numDecodings1(const string& s,int i){
        //为0则此分支不合理返回0
        if(s[i]=='0'){
            return 0;
        }
        return s[i]=='*'?9:1;
    }
    int _numDecodings2(const string& s,int i){
        if(s[i]=='0'){
            return 0;
        }
        //当前步长为2
        if(i+1<s.size()&&s[i]=='*'){
            if(s[i+1]=='*'){
                //9+6=15
                return 15;
            }else if(s[i+1]>='0'&&s[i+1]<='6'){
                return 2;
            }else{
                return 1;
            }
            
        }else if(i+1<s.size()&&(s[i]=='1'||s[i]=='2')){
            if(s[i+1]=='*'){
                if(s[i]=='1'){
                    return 9;
                }else{
                    return 6;
                }
            }else if(s[i]=='1'||(s[i]=='2'&&s[i+1]<'7')){
                return 1;
            }else{
                return 0;
            }
        }else{
            return 0;
        }
    }
};