share java solution!


  • 0
    T
    public class Solution {
        public int numDecodings(String s) {
            if(s==null || s.length()<1) return 0;
            if(s.charAt(0)=='0'){
                return 0;
            }
            
            int len=s.length();
            Integer[] dp=new Integer[len];
            
            return helper(dp,s.length()-1,s);
        }
        
        public int helper(Integer[] dp,int index,String s){
            if(index==0){
                dp[0]=1;
                return 1;
            }
            
            if(dp[index]!=null){
                return dp[index];    
            }else{
                int sum=0;
                
                int num=s.charAt(index)-'0';
                if(num!=0){
                    sum+=helper(dp,index-1,s);
                }
                
                num=Integer.parseInt(s.substring(index-1,index+1));
                if(s.charAt(index-1)!='0'&&num<=26&&num>=1){
                    if(index-2<0){
                        sum+=1;
                    }else{
                        sum+=helper(dp,index-2,s);
                    }
                }
                
                dp[index]=sum;
                return sum;
            }
            
            
        }
    }
    

Log in to reply
 

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