Leetcode 91. 解码方法 动态规划

原题链接：Leetcode 91. 解码方法


自己写的代码：

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n,1);
        if(s[n-1]=='0') dp[n-1]=0;
        for(int i=n-2;i>=0;i--)
        {
            if(s[i]!='0')
            {
                string t=s.substr(i,2);
                int tmp=atoi(t.c_str());
                if(tmp>=1&&tmp<=26) dp[i]=dp[i+1]+(i+2<n ? dp[i+2]:1);
                else dp[i]=dp[i+1];
            }
            else 
            {
                if(i-1>=0 && (s[i-1]=='1' || s[i-1]=='2'))
                {
                    dp[i]=0;
                    dp[i-1]=dp[i+1];
                    i--;
                }
                else return 0;
            }
        }
        return dp[0];
    }
};

参考别人的代码：Leecode 91. 解码方法

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        if(s[0]=='0') return 0;
        int res=1,pre=1;
        for(int i=1;i<n;i++)
        {
            int tmp=res;
            if(s[i]=='0')
            {
               if(s[i-1]=='1' || s[i-1]=='2') res=pre;
               else return 0;
            }
            else if(s[i-1]=='1' || (s[i-1]=='2' && s[i]>='1' && s[i]<='6'))
                res+=pre;
            pre=tmp;
        }
        return res;
    }
};