Evolve from recursion to dp


  • 10
    1. Recursion O(2^n)
        int numDecodings(string s) {
            return s.empty() ? 0: numDecodings(0,s);    
        }
        int numDecodings(int p, string& s) {
            int n = s.size();
            if(p == n) return 1;
            if(s[p] == '0') return 0;
            int res = numDecodings(p+1,s);
            if( p < n-1 && (s[p]=='1'|| (s[p]=='2'&& s[p+1]<'7'))) res += numDecodings(p+2,s);
            return res;
        }
    
    1. Memoization O(n)
        int numDecodings(string s) {
            int n = s.size();
            vector<int> mem(n+1,-1);
            mem[n]=1;
            return s.empty()? 0 : num(0,s,mem);   
        }
        int num(int i, string &s, vector<int> &mem) {
            if(mem[i]>-1) return mem[i];
            if(s[i]=='0') return mem[i] = 0;
            int res = num(i+1,s,mem);
            if(i<s.size()-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) res+=num(i+2,s,mem);
            return mem[i] = res;
        }
    
    1. dp O(n) time and space, this can be converted from #2 with copy and paste.
        int numDecodings(string s) {
            int n = s.size();
            vector<int> dp(n+1);
            dp[n] = 1;
            for(int i=n-1;i>=0;i--) {
                if(s[i]=='0') dp[i]=0;
                else {
                    dp[i] = dp[i+1];
                    if(i<n-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) dp[i]+=dp[i+2];
                }
            }
            return s.empty()? 0 : dp[0];   
        }
    
    1. dp constant space
        int numDecodings(string s) {
            int p = 1, pp, n = s.size();
            for(int i=n-1;i>=0;i--) {
                int cur = s[i]=='0' ? 0 : p;
                if(i<n-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) cur+=pp;
                pp = p;
                p = cur;
            }
            return s.empty()? 0 : p;   
        }
    

Log in to reply
 

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