Java DP solution and recursive solution.


  • 1
    Z
    public int numDecodings(String s) {
        if(s.length() == 0) return 0;
        int n = s.length();
        int[] A = new int[n+1];
        A[n] = 1;
        A[n-1] = s.charAt(n-1) == '0'?0:1;
        for(int i=n-2;i>=0;i--){
            if(s.charAt(i) != '0'){
                A[i] = A[i+1];
                int val = Integer.parseInt(s.substring(i,i+2));
                if(val > 0 && val <=26){
                    A[i] += A[i+2];
                }
            }
        }
        return A[0];
    }
    

    use recursion

    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    public int numDecodings(String s) {
        if(s.length() == 0) return 0;
        return decode(s,0);
    }
    public int decode(String s,int i){
        if(i == s.length()) return 1;
        if(i == s.length()-1) return s.charAt(i) == '0'?0:1;
        if(map.containsKey(i)) return map.get(i);
        if(s.charAt(i) =='0') return 0;
        int res = decode(s,i+1);
        int val = Integer.parseInt(s.substring(i,i+2));
        if(val > 0 && val <=26){
            res += decode(s,i+2);
        }
        map.put(i,res);
        return res;
    }

Log in to reply
 

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