Commented simple java dynamic programming


  • 0
    Z
    
    /**
     * Dynamic programming: S(i)= f(S(i-1),  S(i-2))
     * function f:  check wether 
     *              1) char i is valid itself, 
     *              2) can char i and i-1 be combinend
     * 
     * if 1) S(i) += S(i-1)
     * if 2) S(i) += S(i-2)
     * 
     */ 
    public class Solution {
        public int numDecodings(String s) {
            if(s == null || s.length() == 0 )
                return 0;
            
            // ns[i] means num of decoding in substring s[0..i]    
            int[] ns = new int[s.length()];
            
            for(int i =0; i < ns.length; i++ ){
                boolean validSingle = isValidSingle(s, i);
                if(validSingle)
                    ns[i] += get(ns, i-1);
                boolean combineable = isCombineable(s, i);
                if(combineable)
                    ns[i] += get(ns, i-2);
                    
                // error!
                if(!(validSingle || combineable))
                    return 0;
                    //throw new IllegalArgumentException("invlaid char at idx " + i);
            }
            
            return ns[ns.length-1];
        }
        
        int get(int[] ns, int i){
            return i >=0 ? ns[i]: 1 /*by definition*/;
        }
        
        boolean isValidSingle(String s , int i){
            char c = s.charAt(i);
            return Character.isDigit(c) && c != '0';
        }
        
        boolean isCombineable(String s, int i){
            if (i == 0)
                return false;
            
            int val = (s.charAt(i -1) - '0' ) * 10 + s.charAt(i) - '0' ;
            return 10 <=val && val <= 26;
        }
        
        
    }
    

Log in to reply
 

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