JAVA DP solution


  • 0
    C
    public class Solution {
        public int numDecodings(String s) {
        /*corner case: when the first char is '0', we cannot decode the string*/
    
            if(s == null || s.length() == 0 || s.charAt(0) == '0') return 0; 
       /*To update the subproblem, we only need the last state and the state before last state*/
            int[] dp = new int[2];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 1; i < s.length(); i++){
                int temp = s.charAt(i) - '0';
    /*If the number at current position is 0, and the last number is 0 too, we cannot decode the string. Also, if the last number is greater than 2, we cannot decode the string*/
                if(temp == 0){
                    if(s.charAt(i-1) == '0' || s.charAt(i-1) > '2') return 0;
                } 
                else{
    /*If the current number is non-zero, but the last number is zero, we could not have more ways to decode the string. So the current state is based on the last state.*/
                    if(s.charAt(i-1) == '0') {
                        dp[i%2] = dp[(i-1)%2];
                    }
    /*If the current number is non-zero, and could combine with the last number to get a number less than or equal to 26, we could have two ways to decode.*/
                    else if(10*(s.charAt(i-1) - '0') + temp <= 26){
                        dp[i%2] += dp[(i-1)%2];
                    }
    /*If the current number is non-zero, but could not combine with the last number to get a number less than or equal to 26,the current state is based on the last state.*/
                    else{
                        dp[i%2] = dp[(i-1)%2];
                    }
                }
            }
            return dp[(s.length() -1)%2];
            
        }
    }
    

Log in to reply
 

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