Share my C++ DP code


  • 0
    X
    class Solution {
    public:
        int helper(string s, int p, vector<int>& flag){
            if(p==s.length()||s[p]=='0'){
                flag[p]=s[p]=='0'? 0:1;
                return flag[p];
            }
    
            flag[p]= flag[p+1]==-1? helper(s, p+1, flag):flag[p+1];
            if(p==s.length()-1)
                return flag[p];
    
            if(s[p]=='1'||(s[p]=='2'&&s[p+1]<='6')){
                flag[p]+= flag[p+2]==-1? helper(s, p+2, flag):flag[p+2];
            }
            return flag[p];
    
        }
    
        int numDecodings(string s) {
            if(s.length()==0)
                return 0;
            vector<int> flag(s.length()+1, -1);
            int res=helper(s, 0, flag);
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.