My Java DP solution


  • 7
    Y

    This is my DP solution for this problem. The code is kind of long, which is not necessary.

    My thought process is like this:

    For the last digit in the string,

    if we take it as an individual letter, then the possibility depends on the rest of the string,

    if we take it along with the last but 1 digit to form one letter (which is from 10 to 26), the possibility depends on the rest of the but the last 2.

    If we sum these 2 possibility, we can get the total possibility.

    So f(s) = f(s-last letter) + f(s - last 2 letters)

    But there are special cases:

    if the last 2 digits are not a letter, which is not from 10 to 26, then f(s) = f(s-last letter)

    if the last digital is 0, which means it has to go with the previous letter, then f(s) = f(s - last 2 letter).

    Then having these on hand, using memorization, we can calculate from the first letter to the end.

    public class Solution {
        public int numDecodings(String s) {
            if(s == null || s.isEmpty()){
                return 0;
            }
            
            if(s.length() == 1){
                if(isZero(s, 0)){
                    return 0;
                }else{
                    return 1;
                }
            }
            
            int[] a = new int[s.length()];
            
            if(isZero(s, 0)){
                return 0;
            }else{
                a[0] = 1;
            }
    
            
            if(isZero(s, 1)){
                if(isLetter(s, 1)){
                    a[1] = 1;
                }else{
                    return 0;
                }
                
            }else if(isLetter(s, 1)){
                a[1] = 2;
            }else{
                a[1] = 1;
            }
            
            for (int i = 2; i < s.length(); i++){
                
                if(isZero(s, i)){
                    if(isLetter(s, i)){
                        a[i] = a[i-2];
                    }else{
                        return 0;
                    }
                    
                }else if(isLetter(s, i)){
                    a[i] = a[i-1] + a[i-2];
                }else{
                    a[i] = a[i-1];
                }
            }
            return a[s.length()-1];
        }
        
        private boolean isZero(String s, int index){
            return s.charAt(index) == '0';
        }
        
        /**
         * return true if it is a 2 digital number < 26
         */
        private boolean isLetter(String s, int index){
            char c1 = s.charAt(index);
            char c2 = s.charAt(index - 1);
            
            if(c2 == '1'){
                return (c1>='0' && c1 <= '9');
            }else if(c2 =='2'){
                return (c1>='0' && c1 <= '6');
            }
            
            return false;
        }
    }

Log in to reply
 

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