[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

Longest Palindromic Substring

1. Example
         
Not DP           s        s
         15 16 17 18
         isPalindrome(s, 16,16), right = left         sine  i =16 %2 == 0

         isPalindrome(s, 17,18),  right = left +1 since i=17 %2 =1

DP
01234567 89
forgee  ks s k e e g f o r
i iiiiiiiiii i=7 i  i  i i  i  i i i
              j       => iter1  , s[i]= s[j] and j-i = 0 <= 1
              i
                 j     => iter2,   s[i] = s[j] and j-i=1 <= 1, palin[7][8] = true
              i
                   j  => iter3, s[i] != s[j]
            i=6
            j
            i
               j
            i
                 j
            i
                    j=>s[i]=s[j] and palin[7][8] = ture => palin[6][9] = true, len = 9-6+1 = 4, substring(6,10)

s= "forgeeksskeegfor"

Longest palindrome substring is: geeksskeeg

2. Implementation
Q1: for i=0
          for  j=i+1
           curr = s.substring(i,j)
            if (   curr.length() > maxLen  )
            maxLen =curr.length() ;
            str = curr;
A1: Time : O(n^2*n isPalindrome), Space:O(1)
Q1:           ss
                kssk
              eksske
            eeksskee
          geeksskeeg
A1: Time:O(n^2), Space:O(n^2)
s[i] = s[j] and res[]
       s[0] res[0]
       s[0] = s[1]


Q1:     a     b      c       c      b        a         d
        0 1 2  3  4  5  6  7  8  9  10 11 12  13
A1: Time: O( 2n-1 gap* n isPalindrome), Space:O(1)

// Center outward
// Time:O(n^2), Space:O(1)
public String longestPalindrome(String s)
{


    
    String res = new String();
    if ( s == null || s.length()== 0)
       return res;



    //  n + n-1  = 2n-1
    for (int  i= 0 ; i < 2*s.length() -1;i++)
    {




         int left = i/2; 
         int right = i/2;
         if ( i%2 == 1 )
             right++;
          


          
         int maxLen = 0;
         String str = lengthOfPalindrome(String s, int left, int right);
         if ( str.length() > maxLen)
         { 
            maxLen = str.length();
            res = str;
         } 


         
    }



    return res;



}


private String lengthOfPalindrome( String s , int left ,int right )
{




    int l = left;
    int r = right;
    //  <-l data-blogger-escaped-r-="">
    while ( l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r) )
    {
           l--;
           r++;
    }





    return s.subString(l+1, r); // l become l-- but it is now l and r become r++ and it's right fit for substring()




}

// Dynamic Programming
// Time:O(n^2), Space:O(n^2)
public String longestPalindrome( String s )
{
    





      String res = new String();
      // validate the input
      if (s== null || s.length() == 0)





      boolean[][] palin = new Boolean[][];
      int maxLen = 0;
      String res = "";
      for (int i = s.length()-1; i>=0 ; i--)
      {
           for (int j = i; j < s.length();j++)
           {
               



               if ( s.charAt(i) == s.charAt(j) &&     
                    (j-i <=1 || palin[i+1][j-1] == true )   )
               {
                    palin[i][j] = true;
                    if ( maxLen < j-i+1)
                    {
                          maxLen = j-i+1;
                          res = s.subStirng(i, j+1);                    
                    }
               }






           }
      }



   
      return res;



}

// REturn length of the longest palindrome string
public int lps_recursive(Stirng s)
{


     return lps(s,0,s.length()-1);


}
private int lps(String s, int left, int right)
{



    if (left > right )
       return 0;
    if (left == right )   
       return 1;



    if ( s.charAt(left) == s.charAt(right))
       return lps(s, left+1, right-1) + 2 ;
    else 
       return Math.max( lps(s,left+1,right), lps(s, left, right-1)  );



}

3. Similar Ones
(H) Shortest Palindrome
(E) Palindrome Permutation
(H)  Longest Valid Parentheses
(M) Longest Common Prefix
(M) Longest Substring Without Repeating Characters
(H) Longest Consecutive Sequece

[Backtracking][Combinations] Letter Combinations of a Phone Number

1. Example

23
for       for ...
2          3       
a    +    d            "ad"
      +    e            "ae"
      +    f             "af"
b    +    d            "bd"
      +    e            "be"
      +    f             "bf"
c    +    d             "cd"
      +    e             "ce"
      +    f              "cf"


Backtracking

sb.append(str.charAt(i));

letterCombinations(digits, index+1, , res);

sb.deleteCharAt(str.length()-1);

Input: Digit String "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd","ce",""cf]

2. Implementation
Q1: first digit String1 and Second digit String2
A1: nested for loop one char to one char pair O(k^n), k average letter of a number and n is the lenght of digit

"23"
3*3 = 3^2 = 9

// Recursive
// Time:O(k^n) , Sapce:O(n)
// List {"ad", "ae", "cf"}, size is dynamic and so it is List
public List letterCombination(String digits)
{


    

     String[] letters = {"abc", "def", "ghi", "mno", "pqrs", "tuv", "wxyz"};


 

     List res = new LinkedList<>();
     // validate the input
     if ( digits == null || digits.length() == 0)
         return res;


     

     StringBuilder sb = new StringBuilder();
     letterCombinations(digits, 0, letters, sb, res);



     
}
private void letterCombinations(String digits, int index, String[] letters, StringBuilder sb, List res)
{
  



     if (index == digit.length() )
     {
         res.add(sb.toString());
         return;
     }




     int number = digits.charAt(index) - '0';
     //String str = getLetters(number);
     String str = null;
     if (digit == 0)
         str = " ";
     else 
         str = letters[digit-2];






     for (int i = 0 ; i < str.length(); i++)
     {
         sb.append(str.charAt(i));
         letterCombinations(digits, index+1, , res);
         sb.deleteCharAt(str.length()-1);
     }




}

private String getLetters(int number)
// Iterative
{
      switch(number)
      {
         case 0:// zero is a SPACE
            return " ";
         case 2:
            return "abc";
            //break;
         case 3:
            return "def";
            //break;
         case 4:
            return "ghi";
            //break;
         case 5:
            return "jkl";
            //break;
         case 6:
            return "mno";
            //break;
         case 7:
            return "pqrs";
            //break;
         case 8:
            return "tuv";
            //break;
         case 9:
            return "wxyz";
            //break;
         default:    
            return "";
      }
}

3. Similar Ones
two entity with single unit, how many combinations

Combination

[Backtracking] Restore IP Address

1. Example

part=1       part2         part3      part4(valid and res.add)
2,       +     5,        
                 55,
                 552X
25,     +     5,
                 52,
                 525X
255,   +     2,     
                 25,
                 255,     +   1,
                                  11,
                                  111,      + 3   X
                                               + 35,V   s.len

s="25525511135"
=>
return [ "255.255.11.135",  "255.255.111.35" ];

2. Implementation
Q1: IP address, 4 parts?
A1: divide into four parts and each part can have one or two or three digit BUT all within the range
=> O(n^3), nested for loop
Q1: recursive , for (int i=1; i<4)
one digit + next recursive call(with current INDEX of string and SECTION Index)
                  one digit + next recursive call
                  two digits + next recursive call
                  three digits + next recursive call
two digits + next recursive call
three digits + next recursive call

Base case : use up all length
how to stop: already four parts
Any digit LEFT?'


// NOTE: the case start < s.length()-1 && part == 4 will just return here 

if ( part == 4 ) {

    String str= s.substring(start); 

    if ( isValid(str) ) 

       res.add(item+"."+str); 

     return; 

}

// NOTE: The reason of i start from 1 is becasue SUBSTRING() 

 for (int i=1; i < 4 && (start+i) <= s.length(); i++ ) { 

 String str = s.substring(start, start+i);

// NOTE : 2552

 if ( str.length() > 3 || str == null) return false;

 // NOTE : 02, 005 

if ( c.charAt(0) == '0' && s.length() > 1 ) return false;

// Time:O(n), Space:O(n) call stack
public List restoreIPAddress(String s)
{ 
      



      List res = new ArrayList();




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



      helper(s, 0, 1, new StringBuidler(),res);




      return res;



}

//private void helper(String s , int start, int part, StringBuilder item, List res)
private void helper(String s, int start, int part, String item, List res)
{





       //if ( (start < s.length()-1 && part == 4) || start >= s.length() )
       //  return;
       //if (start == s.length()-1 && part ==4)
       //  res.add(item.toString());




       
       // Base case
       if ( start >= s.length() )
          return;
       // NOTE: the case start < s.length()-1 && part == 4 will just return here
       if ( part == 4 )
       { 
           String str= s.substring(start);
           if (  isValid(str) )
                res.add(item+"."+str);
           return;
       }

      



       //for (int i = start ; i < start + 3 && start+3 <= s.length() ;i++)
       // NOTE: start+i means string can go to last character
       // NOTE: The reason of i start from 1 is becasue SUBSTRING()
       for (int i=1; i < 4 && (start+i) <= s.length(); i++ )
       {
            
           


           String str = s.substring(start, start+i);
           if ( isValid(str)  )  
           {
               if (   part == 1  ) 
               {
                    helper(s,start+1, part+1, str, res);
               }
               else 
               {
                    helper(s,start+1, part+1, item+"."+str, res);
               }
           }




       }





}
private boolean isValid(String str)
{




      // NOTE :2552
      if (  str.length() > 3 || str == null)
             return false;
      // NOTE : 02, 005
      if (   c.charAt(0) == '0' && s.length() > 1   )
             return false;




      int num = Integer.parseInt(s);
      if ( num >=0 && nums <= 255 )
             return true;




      return false;



}

3. Similar Ones
Decode Ways 12 => ["AB", "L"]
Word Break leetcode=> leet, code
House Robber 1,3,5,7 or 2,4,6,8 or 1,3,6,8
Word search    att, ate, ata, atw
Sudoku Solver 1,2,3,4,5,6,7,8,9 or 2,3,4,5,6,7,1,9,8
N-Queens => Q.....Q or ....QQ.... or Q...Q...

[HashTable][Two pointers] Longest Substring Without Repeating Characters

1.Example
/* 

    index         0 1 2 3 4 5 6 7 8 9 10 11 

                      q p x r  j x  k l  t  z  y   x 

1st round       |              |

2nd round               |                          | 

3rd round                         |                 | 

*/

s="abcabcbb" => longest substring  is "abc", whose length is 3

s="bbbb"=> longest substring is "b", whose length is 1


2. Implementation
Q1: substring ?
A1: substring(0,i), subtring (1,i+1),...
Q1: repeating ?
A1; abca X, cannot have the same letter, .contains(letter),
set.add()=>true, DP[i] = DP[i-1]+1
set.add()=>false,DP[i] = DP[i-1];
DP[i] longest length so far
abcabcbb
a
ab
abc
abcaX
1231
abcabs
1231
abcabcdd=>"abcd"
abcad=>"bcad"

"abcdef"
f!=a, e!=b,c!=d
"abcabcbb"
a!=b,b==b,
Q1: all substring O(n^2), sorted by length O(nlogn), find the one without repeating character O(n)
A1:n^2
Q1: when find the repeated character, how to calculate longest

// O(n^3) total number of substrings n*(n+1)/2 and O(n) for check length and no repeated character
// O(n^2) , sort
// Time:O(n)

public int lengthOfLongestSubstring(String s)
{
     



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

      
       

     /*
    index      0 1 2 3 4 5 6 7 8 9 10 11
               q p x r j x k l t z  y  x
    1st round  |         |
    2nd round        |                 |
    3rd round              |           |
    */

    HashMap map = new HashMap();
    int max = 0; 
    int runner = 0;
    int walker = 0;
    for (; runner < s.length();runner++)
    {
        char c = s.charAt(runner);
        if (  map.containsKey(c)  )
        {
            // Input:"abba"
            // Output:3
            // Expected:2
            // a[3] repeat a[0] BUT walker is on b[2]
            walker = Math.max(walker, map.get(c)+1);
            map.put(c,runner);
        }
        else 
        {
            map.put(c,runner);
        }
        max = Math.max(runner-walker+1, max);
    }

    return max;



       
}

3. Similar Ones
(H) Longest Substring with At Most Two distinct characters

[MAth] Multiply Strings

1. Exmaple
reverse, [i+j]+=[i]+[j], charAt(0)
11*5 =55 reverse 055
a=12
b=23
axb =
c[Index sum = 2len-2] =  a[len-1]*b[len-1] =6
c[index sum = 2len-3] =  a[len-2]*b[len-1] + a[len-1]*b[len-2] = 1*3+2*2=7
c[inde sum = 0]           =  a[0]*b[0] = 1*2=2
    0 1 2
a=111
b = 12
     0  1
[0]*[0] = first digit
[1]*[0]+[0]*[1] = 1 last three digit
[1]*[1]+[2]*[0] = 2 last two digit
[2]*[1] =3 last digit
  222
111
1332=>4 digit = a's digit+ b's digit-1 = 4

2. Implementation
carry =0
int sum = carry + c[]
carry = sum/10;
if (carry ==1)
{
  // res.append("1");
res.append(carry);
}
res.reverse().toString();


sum[i+j] += (int)(n1.charAt(i)-'0')+(int)(n2.charAt(j)-'0');



if (i+1< sum.elngth) 

 sum[i+1]+= carry;


res.reverse().toString();  takes (m+n) time

while ( res.charAt(0)=='0' && res.length() > 1 ) res.deleteCharAt(0);

public String multiply(String num1, String num2)
{





    // validate the input
    if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0)
       return "";





     int[] sum = new int[num1.length()+num2.length()];
     int carry = 0;
     //StringBuilder num1r = new StringBuilder(num1);
     //num1 = num1r.reverse().toString();
     //StringBuidlder num2r = new StringBuilder(num2);
     //num2 = num2r.reverse().toString();
     String n1 = new StringBuilder(num1).reverse().toString();
     String n2 = new StringBuidler(num2).reverse().toString();






     for (int i = 0 ; i < n1.length(); i++)
     {
         for (int j = 0; j < n2.length();j++)
         {
            //sum[i+j] = carry + (int)( n1.charAt(i) - '0')*(int) (n2.charAt(j) - '0');
            //carry = sum[i+j] / 10;
            // NOTE: sum[i+j] is accumulating and not possible to only get digit
            sum[i+j] += (int)(n1.charAt(i)-'0')+(int)(n2.charAt(j)-'0');
         }
     }
     //sum[num1.length()+num2.length()-1] = carry;




     


     StringBuidler res = new StringBuilder();
     //for ( int i = sum.length-1 ; i >=0;i--)
     //   res.append(sum[i]);
     
     for (int i = 0; i < sum.length;i++)
     {



          int carry = sum[i]/10;
          int digit = sum[i]%10;
          if (i+1< sum.elngth)
             sum[i+1]+= carry;



          res.append(digit);



     }
     res.reverse().toString();


   
  

     while ( res.charAt(0)=='0' && res.length() > 1 )
          res.deleteCharAt(0);




   
      //return res.toString().trim();
      return res.toString();   




}
  [2][1][0] 
a= 1  1  1
    [1] [0]
b =  1   2



0 +[0][0] 0
c +[0][1] 1
c +[1][0] 1
c +[1][1] 2
c +[2][0] 2
c+ [2][1] 3
c[2+3-1] = c XXX

3. Similar ones
(M) Add Two Numbers
(E) Plus One
(E) Add Binary

[Integer To] Integer to English Words

1. Example
PREPEND, larger, later
// check hundred, >99

// check <= 99 

// check 1000

Input:123
Output:"OneHundredTwentyThree"
Expected:"One Hundred Twenty Three"
Add space before words, like " Hundred"
non-negative, Given input is guaranteed to be less than 2^31-1

123-> "One Hundred Twenty Three"
12345->"Twelve Thousand Three hundred Forty Five"
1234567->"One Million Two Hundred Thirty Four Thousand Sixty Seven"

2. Implementation
Q1: String of unit?
A1: a strign array
Q1: how to divide a number ?
A1: > thousand, < thousand;  > million ,< million; ans 2^31-1 = 2147 48 3647 billion
> billion, < billion
Q1: Left to right or right to left?
A1: PREPEND

int i = 0;

// check if it is thousand, million, billion 

while ( num != 0) {

 if ( num%1000 != 0) 

res = threeDigitToWords( num % 1000 ) + map3[i] + res;

 i++;

 num/=1000; 

}

//NOTE :
// check hundred, >99

 if (num > 99)

 {

 res = map1[num/100] + HUNDRED; 

 } 

 num%= 100;



// check <= 99 

 if ( num < 20)

 res +=map1[num]; 

 else 

 res+= map2[num/10]+ map1[num%10];

// check 1000
if ( num%1000 != 0 )

 res = threeDigitToWords( num % 1000 ) + map3[i] + res;
String[] map3 = new String[]{""," Thousand"," Million"," Billion"}; 

// avoid digit 0
String[] map2 = new String[]{"",""," Twenty"," Thirty"," Forty"," Fifty"," Sixty"," Seventy"," Eighty"," Ninety"};

// Avoid digit 0 and 1

// Time:O(m), number of digits
public class Solution 
{



     String[] map1 = new String[] {"", " One"," Two"," Three"," Four"," Five"," Six"," Seven"," Eight"," Nine"," Ten"," Eleven"," Twelve"," Thirteen"," Fourteen"," Fifteen"," Sixteen", " Seventeen", " Eighteen"," Nineteen"};
     String[] map2 = new String[]{"",""," Twenty"," Thirty"," Forty"," Fifty"," Sixty"," Seventy"," Eighty"," Ninety"};
     String[] map3 = new String[]{""," Thousand"," Million"," Billion"};
     final String HUNDRED = " Hundred";




     public String threeDigitToWords(int num)
     {//0~999




          String res = "";




          // check hundred
          if (num > 99)
          {
               res = map1[num/100] + HUNDRED;
          }
          num%= 100;




          // check < 99
          if ( num < 20) 
               res +=map1[num];
          else
               res+= map2[num/10]+ map1[num%10];

      


          return res;



     }



     public String numberToWords(int num)
     {

          

           // validate the input
           if ( num == 0) return "Zero";
           String res = "";
            



           int i = 0;// check if it is thousand, million, billion
           while (   num !=  0)
           {
                 if ( num%1000 != 0)
                     res = threeDigitToWords(  num % 1000 ) + map3[i] + res;
                 i++;
                 num/=1000;
           }



           return res.trim();


     }
     


}

3. Similar Ones
(M) Integer to Roman