Evolve from recursion to dp


  • 24
    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;   
        }
    

  • 0

    Implementing your idea in Java, I think this should be top 1 post, if we show our thinking process like this, we could get a strong hire estimation in the interview.
    #2 Memoization O(n), #2 in Java doesn't pass LC's time complexity check since LC probably has more restrict requirements for Java, but I test the code in eclipse and it's correct.

    public int numDecodings(String s) {
            if(s == null || s.length() == 0) return 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            return dfs(s, map, 0);
        }
        
        public int dfs(String str, HashMap<Integer, Integer> map, int index){
            if(index == str.length()){
                return 1;
            }
            if(map.containsKey(index)) {
                return map.get(index);
            }
            if(str.charAt(index) == '0') {
                map.put(index, 0);
                return 0;
            }
            int res = dfs(str, map, index + 1);
            if(index + 1 < str.length() && (str.charAt(index) == '1' || (str.charAt(index) == '2' && str.charAt(index + 1) < '7'))){
                res += dfs(str, map ,index + 2);
            }
            return res;
        }
    

    #3 dp O(n) time and space

    public int numDecodings(String s) {
            if(s == null || s.length() == 0) return 0;
            int n = s.length();
            int [] dp = new int [n + 1];
            dp[n] = 1;
            for(int i = n - 1; i >= 0; i--) {
                if(s.charAt(i) == '0'){
                    dp[i] = 0;
                }else{
                    dp[i] = dp[i + 1];
                    if(i + 1 < s.length() && (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) < '7'))){
                        dp[i] += dp[i + 2];
                    }
                }
            }
            return dp[0];
        }
    

    #4 dp constant space

    public int numDecodings(String s) {
            if(s == null || s.length() == 0) return 0;
            int n = s.length();
            int pp = 0;
            int p = 1;
            for(int i = n - 1; i >= 0; i--) {
                int cur = s.charAt(i) == '0' ? 0 : p;
                if(i + 1 < s.length() && (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) < '7'))){
                    cur += pp;
                }
                pp = p;
                p = cur;
            }
            return p;
        }
    

Log in to reply
 

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