DP java solution , beats 92%


  • 0
    J

    This basic idea are d(i)=d(i-1)+d(i-2),but there should be some prerequest.
    if(i can be encode){
    d(i)+=d(i-1)}
    if(i,i-1 can be encode){
    d(i)+=d(i-1)
    }

    Coding are below
    //==================================
    public class Solution {
    public int numDecodings(String s) {
    if(s==null||s.length()==0){
    return 0;
    }
    if(s.charAt(0)=='0'){
    return 0;
    }
    if(s.length()==1){
    return 1;
    }
    char[] str=s.toCharArray();
    int[] nums=new int[str.length];
    if(str[1]=='0'&&!encode(str[0],str[1])){
    return 0;
    }//code before here are deal with illegel input
    nums[0]=1;
    if(encode(str[0],str[1])&&str[1]!='0'){
    nums[1]=2;
    }else{
    nums[1]=1;
    }
    // core code start
    for(int i=2;i<str.length;i++){
    if(str[i]==0&&!encode(str[i],str[i-1])){
    return 0;
    }
    if(!(str[i]=='0')){
    nums[i]+=nums[i-1];
    }
    if(encode(str[i-1],str[i])){
    nums[i]+=nums[i-2];
    }

       }
       //core code end
       return nums[str.length-1];
    }
    private boolean encode(char a,char b){
        if(a=='0'||a>'2'||(a=='2'&&b>'6')){
            return false;
        }else{
            return true;
        }
    
    }
    

    }


Log in to reply
 

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