[DP] Decode Ways

1. Example
Separate OR Combine
1-26
NOT INCLUDED 0 and >27

s[0]=0                                     =>0

  1,2+0                                    => res_2
 >3+ 0                                     => 0


0 or 3          + 1-9                   => res_1
  |-> 2          + 7-9                   => res_1
       |-> 1     + 1-9 and 2+ 1-6 => res_1 + res_2
   

0=> s[0] == 0, s[i]==0 , s[i-1] ==0
s[i] == 0 
 s[i-1]=1 or2    =>res_2
!(s[i-1]=1 or2) => 0
>27 =>
01-09 or 31-39...91-99=>res_1
27,28,29=>res_1,11-19,21-26=>res_1+res_2
s[i] != 0 
s[i-1] =0 || s[i-1]= 3   =>res_1
!(s[i-1] =0 || s[i-1]= 3)  &&     s[i-1]=2&&s[i]=7-9  => res_1
!(s[i-1] =0 || s[i-1]= 3)   &&  !(s[i-1]=2&&s[i]=7-9)=> res_1+res_2
1.validate the input(s[i-1] = 0)
0=>0

2. for loop case(s[i]==0)
if case,     1,2+0=>res_2
else case, >3+ 0=>0

3. for loop case(s[i]!=0)
27,28,29 => res_1

21,....26 => res_1 + res_2
11,....19

01,02,...,09(s[i-1] = 0)
31,32,...,39
..                 => res_1
91,........,99

A->1
B->2
..
Z->26

s="12"
-> "AB"(1  2) or "L" (12)


2. Implementation
Q1: separate or combine?
A1: 12 can separate and can combine
s[0] =0 => 0 ways
otherwise 1

 i=1, s[1] =2, since s[0] <3 and s[1] <7,
s[0], s[1]  ways is res[0]
or s[0]s[1]  ways is res[-1]

s[i] <= 2 and s[i+1] =0    => only can combine
s[i] <= 2 and s[i+1] <7    => can combine and can separate
s[i] <= 2 and s[i+1] >=7  => only can separate

s[i] > 2   and s[i+1] = 0   => 0
s[i] > 2   and s[i+1] < 7   => only can separate
s[i] > 2   and s[i+1] >=7  => only can separate

public int numDecodings( String s )
{
   



     //validate the input
     if ( s == null || s.length() ==0 || s.charAt(0) == '0')
            return 0;

   


     int res_2 =1;
     int res_1 =1;
     int res = 1;




     // Case 1:                     s[i] = 0,
     // Case 1-1, 1,2             + 0         => res[i-2]
     // Case 1-2, 3,4,5,6,7,8,9   + 0         => 0

     // Case 2:                     s[i] != 0
     // Case 2-1: 0,              + 1,...,8,9 => res[i-1] @
     // Case 2-1: 1,              + 1,...,8,9 => res[i-1] + res[i-2]
     // Case 2-2: 2               + 1,...,6   => res[i-1] + res[i-2]
     // Case 2-3: 2               + 7,8,9     => res[i-1] @
     // Case 2-4: 3-9             + 1-9       => res[i-1] @

     // Case 3:  s[i] < 7, + 1,2,3,4,5,6,7
     for (  int i = 1 ; i < s.length() ; i++  )
     {
          if ( s.charAt(i) == '0' )
          {
               if (  s.charAt(i-1) == '1' || s.charAt(i-1) == '2' )
                    res = res_2;
               else // 3,4,5,5...9+0, not a case, no way to decode
                    // res = 0;
                    return 0;
          }
          else
          {
               //if (  s.charAt(i) >= '7' &&  s.charAt(i-1) == '1'  )
               //     res = res_1 + res_2;
               //else
               if ( s.charAt(i-1) == '0' || s.charAt(i-1) >='3')
                      res = res_1;  //@
               else
               {
                      if ( s.charAt(i-1) == '2' && s.charAt(i) >= '7'&& s.charAt(i) <= '9' )
                      {
                           res = res_1;  //@
                      }
                      else
                      {
                           res = res_1 + res_2;
                      }
               }        
          }
          res_2 = res_1;
          res_1 = res;
     }




     return res_1;



}

3. Similar Ones