DP Java simple :)


  • 2
    S
     public int numDecodings(String s) {
            if( s.compareTo("") == 0) return 0;
            
            int[] ways = new int[s.length()+1];
            ways[s.length()] = 1;
            int prev = -1;
            
            for (int i = s.length()-1;i >= 0;i--) {
                int cur = Character.getNumericValue(s.charAt(i));
                if (cur != 0) {
                    ways[i] = (prev !=-1 && cur*10+prev<=26) ? ways[i+2]+ways[i+1] : ways[i+1];
                }
                prev = cur;
            }
            
            return ways[0];
        }

  • 0
    S

    @sara13 thanks for sharing.

    just for understand , i write a solution from positive direction to loop the str,but not simple

    public int numDecodings(String s) {

        int len=s.length();
        
        if(len==0)
            return 0;
        
        
        int[] ways = new int[s.length()+1];
        ways[0] = 1;
        int prev = -1;
        
        for (int i = 1;i <=len;i++) {
            int curr = Character.getNumericValue(s.charAt(i-1));
            
          if(curr==0){
              
              if(prev==-1 || prev==0 || prev*10+curr>26){
                  return 0;
              }
              ways[i]=ways[i-2];
              
          }else{
              if(prev==-1){
                  ways[i]=ways[i-1];
              }else if(prev==0 ){
                  ways[i]=ways[i-2];
              }else if(curr+prev*10<=26){
                  ways[i]=ways[i-1]+ways[i-2];
              }else{
                  ways[i]=ways[i-1];
              }
              
          }
            
            prev = curr;
        }
        
        return ways[len];
        
    }

  • 0

    awesome solution, very readable


Log in to reply
 

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