Java DP with 2 vars. easy. commented.


  • 0
    Z
        public int numDecodings(String s) {
            if(s== null || s.length() ==0)
                return 0;
            
            /*by definition*/
            int prev = 1; 
            int prevPrev = 1; 
            
            for(int i =0; i < s.length(); i ++){
                int cur = 0;
                /*one char matching*/
                int oneChar = Integer.parseInt(s.substring(i, i+1));
                if(1 <= oneChar  && oneChar <= 9)
                    cur += prev;
                
                /*two  char matching*/
                if(i > 0){
                    int twoChar = Integer.parseInt(s.substring(i-1, i+1));
                    if(10 <= twoChar  && twoChar <= 26) 
                        cur += prevPrev;    
    
                }
                
                if(cur == 0)// bad input
                    return 0;
                    
                // move forward
                prevPrev = prev;
                prev = cur;
            }
            
            return prev; 
        }
    

Log in to reply
 

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