LeetCode OJ:Decode Ways

Decode Ways  
A message containing letters from  A-Z  is being encoded to numbers using the following mapping:

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

Given an encoded message containing digits, determine the total number of ways to decode it.
For example, Given encoded message  "12" , it could be decoded as  "AB"  (1 2) or  "L"  (12).
The number of ways decoding  "12"  is 2.
アルゴリズムの考え方:
直接dfsタイムアウト、記録パスを追加する必要があります

class Solution {
public:
    bool isValid(string s){
        if(s[0]=='0')return false;
        int sum=0;
        for(int i=0;i<s.size();i++){
            sum*=10;
            sum+=s[i]-'0';
        }
        return sum>=1&&sum<=26;
    }
    int dfs(vector<int> &dp,string &s,int start){
        if(start>=s.size())return 1;
        if(dp[start]!=-1)return dp[start];
        if(s[start]=='0')return 0;
        int sum=0;
        for(int i=start;i<s.size()&&i-start<2;i++){
            string sub=s.substr(start,i-start+1);
            if(isValid(sub)){
                sum+=dfs(dp,s,i+1);
            }
        }
        dp[start]=sum;
        return sum;
    }
    int numDecodings(string s) {
        if(!s.size())return 0;
        vector<int> dp;
        dp.assign(s.size(),-1);
        return dfs(dp,s,0);
    }
};

動的計画:

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty()||s[0]=='0')return 0;
        
        int prev=0;
        int cur=1;
        
        for(size_t i=1;i<=s.size();++i){
            if(s[i-1]=='0')cur=0;
            
            if(i<2||!(s[i-2]=='1'||
                (s[i-2]=='2'&&s[i-1]<='6')))prev=0;
            
            int tmp=cur;
            cur=prev+cur;
            prev=tmp;
        }
        return cur;
    }
};