public static int numDecodings(String s){
  if (s == null || s.length() == 0) {
    return 0;
  }
  int len=s.length();
  int[] ways=new int[len + 1];
  ways[0]=1;
  ways[1]=s.charAt(0) == '0' ? 0 : 1;
  for (int i=2; i <= len; i++) {
    int code1=Integer.valueOf(s.substring(i - 1,i));
    int code2=Integer.valueOf(s.substring(i - 2,i));
    ways[i]=(code1 != 0 ? ways[i - 1] : 0) + (code2 <= 26 && code2 > 9 ? ways[i - 2] : 0);
  }
  return ways[len];
}

public static int numDecodings ( String s ) { if ( s == null || s . length ( ) == 0 ) { return 0 ; } int len = s . length ( ) ; int [ ] ways = new int [ len + 1 ] ; ways [ 0 ] = 1 ; ways [ 1 ] = s . charAt ( 0 ) == '0' ? 0 : 1 ; for ( int i = 2 ; i <= len ; i ++ ) { int code1 = Integer . valueOf ( s . substring ( i - 1 , i ) ) ; int code2 = Integer . valueOf ( s . substring ( i - 2 , i ) ) ; ways [ i ] = ( code1 != 0 ? ways [ i - 1 ] : 0 ) + ( code2 <= 26 && code2 > 9 ? ways [ i - 2 ] : 0 ) ; } return ways [ len ] ; }
dp . o ( n ) time , o ( n ) space . suppose the length of the string is n . recurrence relation : number of decode ways at length n related to number of decode ways at previous lengths . if we can decode the last digit , then ways [ n ] + = ways [ n - 1 ] . if we can decode the last two digits , then ways [ n ] + = ways [ n - 2 ] . base case : ways [ 0 ] = 1 , means only one way when string length is zero . ways [ 1 ] = 0 or 1 , depending on the only digit is 0 or non - zero .
