[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

[Anagram][Hash Table] Group Anagram

1. Example
anagram means after sorted they have the same string
Collections.sort(item);
Group anagrams together

s= ["eat", "tea", "tan", "ate", "nat", "bat"]
Return
[
["ate", "eat", "tea"]
["nat", "tan"],
["bat"]
]


2. Implementation
Q1: Return List<List<String>>?
A1: since the size of string array is dynamic

Input:["tea","and","ate","eat","den"]
Output:[["tea","ate","eat"],["and"],["den"]]
Expected:[["den"],["and"],["ate","eat","tea"]]
NOTE: each inner list's elements must follow the lexicographic order 
==> Collections.sort(item);
NOTE:
for (List<String> value: map.values()) {

// //Time :O(m*n) or O(m+n) , m is length of string and n is number of string in string array
//Time:O(n* mlogm), n is size of string array, m is the length of each string, assume they are the same
public List> groupAnagrams(String[] strs)
{




      List> res = new List>();
      if (strs == null || strs.length == 0)
          return res;




      
      //HashTable> table = new HashTable> ();
      HashMap<String, List<String>> map = new HashMap<String, List<String>>();




      for (int i = 0; i < strs.length; i++)
      {

           


           char[] charArr = strs[i].toCharArray();
           Arrays.sort(charArr);
           String str = new String(charArr);

           



           //if ( table.containsKey() )
           if (map.containsKey(str))
           {
               //table.get(key).add( strs[i]);
               map.get(str).add( strs[i] );
           }
           else 
           {
               //for (int j = 0 ; j< strs[i];j++)
               ///{
                //(int) (strs[i].charAt(j)-'a')
              // }
              List<String> item = new ArrayList<String>();
              item.add(strs[i]);
              //table.put(, item);
              map.put(str, item)
           }




        
      }






      //NOTE:return all the map values,(map.keySet())
      for (List value: map.values())
      {
           List<String> item = new ArrayList<String>(value);





           Collections.sort(item);





           if (item.size() >0)
              res.add(item);
          
      }



      return res;

    

}

3. Similar Ones
(E) Valid Anagram
(E) Group Shifted Strings

[Math]Integer to Roman

1. Exmaple
// NOTE: avoid call stack don't put call within loop
s= 1700 = >"MDCC"

s= 24 => "XXIV"

s= 19 => "XIX"

s= 900=>"CM"


2. Implementation
Q1: care for for number 4 and 9
// NOTE: avoid call stack don't put call within loop
List digits = new ArrayList();

digits.add(num/divisor);


StringBuilder res = new StringBuilder(); 

res.append( convert(digits.get(0), 'M', '','') ); 

res.append( convert(digits.get(1), 'C', 'D', 'M') ); 

 res.append( convert(digits.get(2), 'X', 'L', 'C') ); 

 res.append( convert(digits.get(3), 'I', 'V', 'X') );

// NOTE: start from 5 can merge case 5 into here

 for (int i = 5; i< digit;i++)
default: //return ""; 

 // NOTE: return string all in bottom, so just BREAK 

default:

 break;

public String intToRoman(int num)
{



     //validate the input
     if ( num < 0 )
          return "";




         
     int divisor = 1000;
     



     // NOTE: use a data structure to store the digits you want to print out
     List digits = new ArrayList();




     while ( divisor > 0)
     {
         //int digit = num /divisor;
         digits.add(num/divisor);

         // NOTE: avoid call stack don't put call within loop
         //if ( divisor == 1000 )
         //{
         //     res.append();
         //}
         //else if ( divisor == 100)
         //{
         //     res.append();
         //}
         //else if ( divisor =10 )
         //{
         //     res.append();
         //}
         //else if ( divisor ==1)
         //{
         //     res.append();
         //} 


         //num/=divisor;
         num%= divisor;
         divisor/=10;

     }



    

     StringBuilder res = new StringBuilder();
     res.append( convert(digits.get(0), 'M', '','') );
     res.append( convert(digits.get(1), 'C', 'D', 'M') );
     res.append( convert(digits.get(2), 'X', 'L', 'C') );
     res.append( convert(digits.get(3), 'I', 'V', 'X') );


     
     return res.toString();



}
public String convert (int digit, char one, char five, char ten)
{
       
      StringBuilder sb = new StringBuilder();
 
     
      switch(digit)
      {
           case 1:
           case 2:
           case 3:
               for ( int i =0; i < digit ; i++)
               {
                   sb.append(one);
               }        
               break;
           case 4:
               sb.append(one);
               sb.append(five);
               break;
           case 5:
               //sb.append(five);
               //break;
           case 6: 
           case 7:
           case 8:
               sb.append(five);
               //for (int i=0;i< digit -5;i++)
               // NOTE: start from 5 can merge case 5 into here
               for (int i = 5; i< digit;i++)
               {
                   sb.append(one);
               }
               break;
           case 9:
               sb.append(one);
               sb.append(ten);           
               break;
           default:
               //return "";
               // NOTE: return string all in bottom, so just BREAK
               break;
      }


      return sb.toString();


}

3. Similar Ones
(E) Roman to Integer
(M) Integer to English Words

[Two Pointers] Implement strStr()

1. Example

for (int i = 0 ; i <= haystack.length() - needle.length() ; i++)

     for (int j = 0; j < needle.length(); j++)

           haystack[i+j] == needle[j]

NOT EVERYTIME i++
while ( i <=  haystack.length() - needle.length() )
     for (int j = 0 ; j < needle.length();j++)
           haystack[i+j] == needle[j]
         if  haystack and needle first char not match 

             i++;

             break;

         else 
             i +=  j - next[j-1];
             break;


"issip"
00120

012345678910
"mississippi"
"issip"
  "issip" i += j - next[j-1] = 4 -2= 2
issip
issipi
KMP
1. Prefix table
A C A C  A G T
0  0  1  2  3  0  0
first char no shift (0)
for each char, find the same letter before it and if found, last char's shift +1 
                       cannot find the same letter before it, no shift (0)
i + j - ( prefixtable[j]-1 )


for (int i = 1; i < needle.length(); i++) {
int index = next[i - 1];
while (index > 0 && needle.charAt(index) != needle.charAt(i)) {
index = next[index - 1];
}

if (needle.charAt(index) == needle.charAt(i)) {
next[i] = next[i - 1] + 1;
} else {
next[i] = 0;

}

N A N O

0  0  1  0

2. How to do the skip (shift previous same letter(from prefix table) to mismatch index)

A C A C  A G T
0  0  1  2  3  0  0


i=0 1  2    3
A  C  A    T.....................
A1C1A2  C2
                X
          i=2
          A1 C1
          i = i+j - next[j-1] = 0+3 - 1 =2

String compare amongst more than two use INDEX to record matched length
Succeed go to the end and not succeed break, use BOOLEAN FLAG
return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack

n="sub"  h ="submarine"=> return 0
n="ood" h = "food" => return 1

2. Implementation
Q1: compare char to char from one to the other?
A1: Time:O(n*m), how many iterations,  index 0 to index 0 and needle.length() to 0+needle.length
https://www.youtube.com/watch?v=2ogqPWJSftE

public int strStr(String haystack, String needle)
{




    // validate the input
    if (haystack == null || needle == null || neelde.length() ==0)
        return 0;
    if ( needle.length() > haystack.length() )
        return -1;
     




    int[] next = getNext(needle);
    int i = 0;




    // NOTE: since i will jump, we use while loop
    while (  i <= haystack.length() - needle.length()  )
    {
        



        boolean successFlag = true;

        


        for ( int j = 0 ; j < needle.length() ; j++) {
              
              // First letter mismatch, regular shift
              if (  needle.charAt(0)  != haystack.charAt(i)  )
              {
                  successFlag = false;
                  i++;
                  break;
              }
              // Other letter mismatch, jump shift
              else if (   needle.charAt(j) != haystack.charAt(i+j)   )
              {
                   successFlag = false;
                   // NOTE: 
                   i = i + j - next[j-1];
                   break;
              }

        }





        if ( successFlag )
            return i;




    }
    


    
    return -1;



    
}
// Calculate the prefix table,called next table here 
public int[] getNext(String needle)
{




      int[] next = new int[needle.length()];
      next[0] = 0;




      for (int i =1 ; i < needle.length(); i++)
      {
             


             
             int index = next[i-1];




             // Case1: index > 0, search back to find same letter 
             while ( index > 0 && needle.charAt(index) != needle.charAt(i) )
                   index = next[index-1];
             




             //Case2: index=0 or others, compare with the index letter and based on it plus 1
             if (needle.charAt(index) == needle.charAt(i))
                   next[i] = next[i-1] + 1;
             else 
                   next[i] = 0;





      }
        

 

      return next;
 


     
}

// Time:O(m*n), Space:O(1)
public int strStr( String haystack, String needle)
{

      // Validate the input
       if (haystack == null || needle == null || needle.length() == 0)
           return 0;
       if (needle.length() > haystack.length())
           return -1;


       
      //int index = 0;
      //NOTE: haystack.length()-1==== needle.length()-1
      //  hay-1-needle+1=hay-needle(include)    0(include)
      for (int i = 0 ; i <= haystack.length() - needle.length() ; i++)
      {



         // NOTE: to record in case, once false, we are done
         boolean successFlag = true;




         for (int j =0; i < needle.length(); j++)
         {
               if (needle.charAt(j)!=haystack.charAt(i+j)) 
               {
                  break;
                  successFlag = false;
               }
               //index++;                   
         }




         //if (index == needle.length())
         //      return i;
         if (successFlag)
            return i;




      }


      return -1;


}

// Time:O(m+n), Space:O(1)
public int strStr(String haystack, String needle)
{





     // validate the input
     if ( haystack==null || needle == null || neelde.length()==0)
        return 0;
     if ( needle.length() > haystack.length() )
        return -1;






     // NOTE: when doing shift in the haystack, every s            hift remvoe previous first char and add a new last char
     // NOTE: abc = 0*29^2 + 1*29^1 + 2*1
     int base = 29;
     int temp = 1;
     int hashcode = 0;
     for ( int i = needle.length()-1; i >= 0 ; i++)
     {
          hashcode+ = (int)(needle.charAt(i)-'a')*temp;
          temp*=base;
     }





     int temp2 =1;
     int hashcode2 = 0; 
     for(int j = needle.length()-1;j>=0;j++)
     {
         hashcode2+= (int)(haystack.charAt(i)-'a')*temp2;
         temp2*=base;
     }





     if (hashcode == hashcode2)
        return 0;






     temp2/=base;
     //for (int i = 1; i <= haystack.length() - needle.length();i++)
     //{
     //    hashcode2 = (hashcode2 - haystack.charAt(i-1)*temp2)*base + haystack.charAt(i+needle.length()-1);
     //    if (hashcode == hashcode2)
     //         return i;
     //}
     // NOTE: start form the last new element
     for (int i=needle.length(); i < haystack.length();i++)
     {
           hashcode2 = ( hashcode2 - haystack.charAt(i-needle.length()*temp2) )*base + haystack.charAt(i);
           return i-needle.length()+1;
     }




     return -1;




     
}

3. Similar ones
(H) Shortest Palindrome

[Math] Roman to Integer

1. Example
Input is guaranteed to be within the range from 1 to 3999

s = "MDCC"=> 1700

s= "XXIV"=>24

s= ""XIX" => 19

s= "CM"=>900

I      V       X
1      5      10
X      L      C
10     50    100
C      D     M
100 500    1000

2. Implementation
Q1: check character and decide what value, what if something like IX
A1: whenever you are at unit 1,10,100 check to see if next are 5,10(for 1),50,100(for 10),,500,1000(for 100)

public int romanToInt(String s)
{

       

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



       s = s.trim();
       if (s.length()==0)
            return 0;

     

       int res = 0;
       for (int i = 0 ; i < s.length(); i ++) 
       {
            char c= s.charAt(i);
            switch(c)
            {






                 case 'I':
                     if ( i+1 < s.length() &&( s.charAt(i+1) == 'V' || s.charAt(i+1)=='X') )
                     {
                        res-=1;
                     }
                     else
                        res+=1; 
                     
                     break;
                 case 'X':
                     if ( i+1 < s.length() &&( s.charAt(i+1)=='L' || s.charAt(i+1)=='C'  ) )
                        res-=10;
                     else 
                        res+= 10;
                     break;
                 case 'C':
                    if ( i < s.length() -1 && (s.charAt(i+1)=='D' || s.charAt(i+1)=='M') )
                    {
                        res -= 100;
                    }
                    else 
                    {
                        res += 100;
                    }
                    break;





                case 'L':
                    res += 50;
                    break;
                case 'D':
                    res += 500;
                    break;
                case 'M':
                    res += 1000;
                    break;
                default:
                    return 0;

            }

       }
}

3. Similar Ones (E)  String to Integer (M) Integer to Roman (M) Integer to Number

[Math] String to Integer (atoi)

1. Example
Possibility to break => Use while loop and an IDNEX
Integer.MAX_VALUE =  2147483647
Integer.MIN_VALUE = -2147483648
Long.MAX_VALUE =  9223372036854775807
Long.MIN_VALUE = -9223372036854775808
"+" and "-"
"456"=>456


2. Implementation
Q1: LSB->MSB
A1: start from LSB to MSB and use res = res*10+ current digit
Q1: special character?
A1: trim and check valid >="0" && <="9"

public int myAtoi(String str)
{

    

     // validate the input
     if ( str == null || str.length() == 0 )   
     {
           return 0;
     }




     str = str.trim();





     // NOTE: could be all spaces
     if ( str.length() == 0)
           return 0;





     boolean negFlag = flase;
     //if ( str.charAt(0) == '-')
     //    negFlag =true; 
     // NOTE: could have no sign, so put an index
     int index = 0; 
     if ( str.charAt(0) == '-' || str.charAt(0) == '+' )
     {
          index++;
          if ( str.charAt(0) == '-')
              negFlag = true;
     }





     //// NOTE: 2147483647
     //int number = 0;
     ////for (int i = str.length()-1 ; i >= 1 ; i ++)
     ////for ( int i = 1 ; i < str.length;i++ )
     //// NOTE: couldbe no sign
     //for (int i = index; i < str.length() ; i++ )
     //{
     //    char c = str.charAt(i);
     //    if ( c >= '0' && c <='9' )
     //    {
     //          
     //          if (  i == str.length() -1 && number >= Integer.MAX_VALUE /10  )
     //             number = (negFlag==true)?Integer.MIN_VALUE:Integer.MAX_VALUE; 
     //          else if ( number == Integer.MAX_VALUE/10 )
     //          {
     //              if ( c >= '7' && c <='9' && negFlag == false)
     //                  return Integer.MAX_VALUE;
     //              else if ( c >='8' && c <='9' && negFlag ==true)
     //                  return Integer.MIN_VALUE;
     //          }
     //          else
     //             //number = number*10 + (int)c;
     //             // NOTE: chat to int - '0'
     //             number = number*10 + (int)(c - '0');
     //    }
     //    else 
     //    {
     //          // NOTE:
     //          break;
     //    }
     //}





      
     int number = 0;
     while ( index < str.length())
     {



         if ( str.charAt(index) < '0' || str.charAt(index) > '9' )
            break;
         int digit = (int) (str.charAt(index) - '0');
         



         // NOTE: -(res*10+digit) < Integer.MIN_VALUE
         if (  negFlag &&  res >  -(Integer.MIN_VALUE+digit)/10  )
               return Integer.MIN_VALUE;
         // NOTE: res*10+digit    > Integer.MAX_VALUE
         else if ( !negFlag && res >  (Integer.MAX_VALUE-digit)/10  )
               return Integer.MAX_VALUE;


       
         number = number*10+digit;
         

        

         index++;



     }









     //return number ;
     return negFalg?-number:number;



     
}

3. Similar Ones
(E) Reverse Integer
(H) Valid Number

[Longest] Longest Common Prefix

1. Example
INSTEAD OF USING A SUBTRING TO MATCH USE INDEX
str[0] as a basis and use append to avoid confusion over using subtring index

s= { "MAU", "MAKAN", "MALAM"}
there are two common prefixes of MAU, which are: "M" and "MA"
Among these, the Longest Common Prefix is "MA" which has a length of 2


2. Implementation
Q1: start from the first word, substring(0,i)i=1~ len
A1; compare it with the rest of string same length,
E.g., M len =1, check i=1 with M and M
MA len =2, check i =2 with MA and MA
MAU len =3, check i=3 wiht MAK and MAL => false
O(string len*array length)


Runtime Error Message:Line 62: java.lang.StringIndexOutOfBoundsException: String index out of range: 1
Last executed input:["cba",""]




Input:["c","c"]
Output:""
Expected:"c"

// Time:O(m*n), Space:O(m), where m is string length and n is numbers of string
public String longestCommonPrefix(String[] strs)
{




    StringBuilder res= new StringBuilder();
    // validate the input
    if ( strs== null || strs.length == 0)
       //return "";
       // NOTE: when loop stop, stringbuilder is what you want
       return res.toString();






    //boolean flag = true;
    //String prefix = new String();
    //for ( int i = 1 ; i <= strs[0].length;i++)
    //{
    //
    //      prefix = strs[0].substring(0,i);
    //      for ( int j =1; j< strs.length; j++)
    //      {
    //             if ( prefix != strs[j].substring(0,i) )
    //             {
    //               flag = false;
    //               break ;
    //             }
    //      }
    //      if (flag == false)
    //        return strs[0].substring(0,i-1);
    //}
    //if (flag == true) 
    //    return strs[0].substring(0,str[0].length);



 

     boolean sameFlag = true;
     int index = 0;




     while ( sameFlag ) 
     {



          for (int i = 0; i < strs.length ;i++)
          {
               if (str[i].length <= index  || strs[i].charAt(index) != str[0])      
               {
                     sameFlag = false;
                     break;
               } 
          }




          if (sameFlag)
          {
               res.append(strs[0].charAt(index));
               index++;
          }       




     }




     return res.toString();




}

3.Similar ones
Longest Series
(H) Longest Valid Parentheses
(M) Longest Palindromic Substring
(M) Longest Substring Without Repeating Characters



(H) Longest Consecutive Sequence

[Palindrome][Two Poitner] Valid Palindrome

1. Example

"A man, a plan, a canal: Panama" is a palindrome
"race a car" is not a palindrome

2. Implementation
valid
palindrome
same char
escape special char: continue
l and r
Q1: how to avoid special character?
A1: if there is not  > 'a' or < 'z', we skip the pointer, meaning ++ or --



In Java, the 'int' type is a primitive , whereas the 'Integer' type is an object.

Runtime Error Message:Line 37: java.lang.StringIndexOutOfBoundsException: String index out of range: 2
Last executed input:".,"
//while (!validAphabet(s.charAt(l))) 

 // l++;StringIndexOutOfBoundsException

 //while( !validAlphabet(s.charAt(r))) 

 // r--;

 if ( !isValid(c.charAt(l)) ) 

 { l++; continue; } 

 if ( !isValid(c.charAt(r)) ) 

 { r--; continue; }

//else 

 // NOTE: if return type is required, no need to ELSE

 return false;

// Time:O(string length), Space:O(1)
public boolean isPalindrome(String s)
{
          

  

      // validate the input
      if (s== null || s.length() == 0)
           //return false;
           return true// nothing always palindrome empty to empty.



      int l = 0;
      int r = s.length()-1;
      //for (int i = 0; i < s.length();i++)
      while ( l < r )
      {






           //while (!validAphabet(s.charAt(l)))
             //   l++;
             //while( !validAlphabet(s.charAt(r)))
             //   r--;
             if (  !isValid(c.charAt(l))  )
             {
                  l++;
                  continue;
             }
             if ( !isValid(c.charAt(r))  )
             {
                  r--;
                  continue;
             }







            //if (validAlphbet(s.charAt(l) && validAlphabet(s.charAt(r)) && s.charAt(l) != s.charAt(r)   )
             // NOTE: Uppercase conversion considered
             if (  !isSame(s.charAt(l), s.charAt(r))  )
                 return false;






           l++;               
             r--;




   }



      return true;


     

}
//private boolean validAlphabet(character c)
private boolean validAlphabet(char c)
{

            //if (  (c <= 'Z' || c <= 'z') && (c' >= 'A' || c >= 'a')  ) 
            // NOTE: could be number
            if (  c >= 'a'&& c <='z' || c >='A'&&c<='Z' || c>='0'&&c<='9' )
                     return true;
            //else
            // NOTE: if return type is required, no need to ELSE 
                     return false;  
}

private boolean isSame(char c1, char c2)
{
       if ( c1 >= 'A' && c1 <= 'Z' )
             c1 = (char)( c1- 'A' +'a');
       if ( c2 >= 'A' && c2 <= 'Z') 
             c2 = (char)(c2 - 'A' + 'a');

       return c1== c2;
}

3. Similar Ones
(E) Palindrome Linked List
(H) Shortest Palindrome
(E) Palindrome Number
(M) Palindrome Partitioning

Length of Last Word

1. Example

s= "Hello World"
return 5( the length of "World")
s= "Hello World "
return 5 (even space happen at the last character)

2. Implementation
Q1: find the last word;
A1: split by space("\\s") and get the last word and return string.length()
split O()
get the last word
Q1: len- last space space, how to find out Space position?
A1: go over all characters and find the last space position, the length of last word would be length
[  length-1   -   (last space index+1)  ] +1


Input:"a"
Output:-1
Expected:1



// NOTE: space may happend at the last character 

// STOP at the last character or last space

 int idx = s.length()-1; 

while ( idx >=0 && s.charAt(idx) == ' ') idx--;

 // NOTE: stop at the last two space

 int idx2 = idx; 

while ( idx2> =0 && s.charAt(idx) !=' ' ) idx2--;

'

// time:O(string length), Space:O(1)
public int lengthOfLastWord(String s)
{



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




       //int spaceIndex = s.length(); 
       //for (int i = 0;i< s.length();i++)
       //{
       //       //if (s.charAt(i) == " ")
       //       // NOTE: is char
       //       if (s.charAt(i) == ' ')
       //           spaceIndex = i;
       //}
       // NOTE: space may happend at the last character
       // STOP at the last character or last space
       int idx = s.length()-1;  
       while ( idx >=0 && s.charAt(idx) == ' ')
           idx--;

        


       // NOTE: stop at the last two space
       int idx2 = idx;
       while ( idx2> =0 && s.charAt(idx) !=' ' )
            idx2--;



       //return (s.length - 1) - (spaceIndex +1) +1 
       //return s.length - spaceIndex -1;
       return idx - idx2;



}

3. Similar Ones

Count and Say

1. Example
Count and Say(when not equal and string builder append)
1,11,21,1211,111221
1 => one 1 => 11
11=> two 1=>21
21=> one two one one=> 1211
so its String.value(count)+"1 or 2" and convert it to int
Given an integer n, generate the nth sequence
like n = 2=> "11"
like n =4 =>"1211"


2. Implementation
Q1: how to count?
A1: an array count array count[value-1], count[0] =? , count[1]=?
Q1: how to iterate?
A1: top-down approach, for loop, return a string, int next = "1", int[] count = new int[2]
str.charAt(i), i < length(), count[(int)(str.charAt(i)-'0')-1]++;



// NOTE: every index correspond to an number

 for (int i =2 ; i <= n; i++ ) // i=1 already appear pre = "1"

// NOTE: when equal, count is already two

 int count =1;



for (int j =1 ;j < pre.length; i++) {

 //count[((int)(pre.charAt(j)-'0')) - 1]++; 

 if ( pre.charAt(j) == pre.cahrAt(j-1) ) count++;

// NOTE: if all the same or the last count 

 res.append(count);

 res.append( res.charAt(pre.length()-1) ); 

 pre = res.toString();

// Time:O(n*string length), Space:O(string length) stringbuilder
public String countAndSay(int n)
{
      



       //vlaidate teh input
       if ( n <= 0 )
              return "";



       
       String pre = "1";// 1st
       //for ( int i = 2 ; i < n; i++)
       // NOTE: every index correspond to an number 
       for (int i =2 ; i <= n; i++ )
       {




             //int[] count = new int[2];
             // NOTE: when equal, count is already two 
             int count =1;
             // NOTE:
             StringBuilder res = new StringBuilder();



             //for (int j = 0 ; j < pre.length; j++)
             // NOTE: contiguous counts
             for (int j =1 ;j < pre.length; i++)
             {
                    //count[((int)(pre.charAt(j)-'0')) - 1]++;
                    if (  pre.charAt(j) == pre.cahrAt(j-1)  )
                       count++;
                    else 
                    {
                          res.append(count);
                          res.append(pre.charAt(j-1));
                          count =1; //reset
                    }
             }
             //StringBuilder sb = new StringBuilder();
             //if (count[0] != 0)
             //{
             //    sb.append(count[0]);
             //    sb.append(1);            
             //}
             //if (count[1] != 0)
             //{
             //    sb.append(count[1]);
             //    sb.append(2);
             //}
             

             
             // NOTE: if all the same or the last count
             res.append(count);
             res.append( res.charAt(pre.length()-1) );
             pre = res.toString();
       }




       return pre;


       
} 

3. Similar Ones
(M) Encode and Decode Strings

[Numbers] Compare Version Numbers

1. Example


0.1 < 1.1 return -1; // like Comparable Class's Comparator's public int compare method, ascending -1
1.2 > 1.1 return 1;// descending , 1
13.37 == 13.37 return 0


2. Implementation
Q1: How to compare if there is a decimal point?
A1: split into two parts from decimal point, then compare the first part if first part is equal, proceed to second part if we have second part




Input:"1", "1.1"
Output:0
Expected:-1

One is len 2 and the other is len 1

which will not compare the second one if len is not balanced

Input:"1.0", "1"
Output:1
Expected:0

Runtime Error Message:Line 102: java.lang.ArrayIndexOutOfBoundsException: 1
Last executed input:"1", "1.0"

Input:"10.6.5", "10.6"
Output:0
Expected:1

// NOTE: dot is a special char in regexes, So you must escape it with a leading backslash, But the leading backslash is a special character, So it must be escaped too, with another leading backslash 

It means "match all chars except newlines"

 String[] v1Arr = v1.split("\\."); 

 String[] v2Arr = v2.split("\\.");

// NOTE: may have more than one decimal point 

 while ( index < v1Arr.length || index < v2Arr.length ) {


// NOTE: same length 

 if ( index < v1Arr.length && index < v2Arr.length) {


// NOTE: v1 longer 

 else if ( index < v1Arr.length ) {

 if ( Integer.parseInt(v1Arr[index]) != 0 ) return 1; } 

 // NOTE: v2 longer 

 else if ( index < v2Arr.length ) {

 if ( Integer.parseInt(v2Arr[index]) != 0 ) return -1; } 

// time:O(length of splitted arry), Space:O(n) array
public int compareVerison(String v1, String v2)
{
        




       // validate the input
       if ( v1== null && v2 == null )
            return 0;
       if ( v1== null || v1.length()==0 )
            return -1;
       if ( v2 ==null || v2.length() == 0)
            return 1;


 

       // http://docs.oracle.com/javase/7/docs/api/java/lang/String.html 
       v1.trim();
       v2.trim();
       // NOTE: Line 75: error: incompatible types: char cannot be converted to String
       //String[] v1Arr = v1.split('.');
       //String[] v2Arr = v2.split('.');
       //String[] v1Arr = v1.split(".");
       //String[] v2Arr = v2.split(".");
       //http://stackoverflow.com/questions/13460595/using-string-split-with-a-decimal-not-working
       // NOTE: dot is a special char in regexes(It means "match all chars except newlines"), So you must escape it with a leading backslash, But the leading backslash is a special character,  So it must be escaped too, with another leading backslash
       String[] v1Arr = v1.split("\\.");
       String[] v2Arr = v2.split("\\.");
       // You may assume that the version strings are non-empty and contain only digits and the . character. 
       // No need to worry no '.'
       int index = 0;
       //while ( index < v2Arr.length && index < v1Arr.length  )
       // NOTE: may have more than one decimal point
       while (  index < v1Arr.length || index < v2Arr.length )
       {              
             // NOTE:http://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html
             //int v1Value = Integer.valuesOf( v1Arr[index]);
             //int v2Value = Integer.valuesOf( v2Arr[index]);
             //int v1Value = Integer.valueOf( v1Arr[index]);
             //int v2Value = Integer.valueOf( v2Arr[index]);
             //if (  v1Value < v2Value )
             //      return -1;
             //else if ( v1Value > v2Value )
             //      return 1;
             //else 
             //{
             //      if (index ==1)
             //          return 0;
             //}
             // NOTE: same length
             if ( index < v1Arr.length && index < v2Arr.length)
             {
                  if (  Integer.parseInt(v1Arr[index]) < Interger.parseInt(v2Arr[index])  ) 
                     return -1;
                  else if ( Integer.parseInt(v1Arr[index]) > Integer.parseInt(v2Arr[index]) )
                     return 1;
             }
             // NOTE: v1 longer
             else if ( index < v1Arr.length ) 
             {
                  if ( Integer.parseInt(v1Arr[index]) != 0 )
                       return 1;   
             }
             // NOTE: v2 longer
             else if ( index < v2Arr.length )
             {
                  if (  Integer.parseInt(v2Arr[index]) != 0 )
                       return -1;
             }


             index++;

       }





       return 0;
       



}

3. Similar ones
Comparable Class Comparator

[Parentheses][Stack] Valid Parentheses

1. Example

s= "()" = > valid
s= "()[]{}"=> valid
s= "(]"=> invalid
s= "([)]"=> invalid


2. Implementation
Q1: parentheses is a pair, How to pair?
A1: Every left parenthesis need a RIGHT parenthesis to pair
Q1: Put left parenthesis onto Stack, and RIGHT comes out?
A1: pop up left parenthesis if RIGHT in in the way, NEED same type of parenthesis
Q1: is there any chance a type of parenthesis's RIGHT one occur very very late?
A1: POSSIBLE, but when that happen, no other parenthesis on top of it, meaning ALL OTHER PARENTHESES MUST HAVE BEEN PAIRED AND POPED OUT



// NOTE: BREAK, don't want to go over below cases

 break;
// NOTE: even equal, need to iterate instead of return 

if (stack.isEmpty() || stack.pop() != '(' ) return false; 

break;
default: break;

// NOTE: Otherwise, FASLE 

 return false;

// Time:O(string length), Space:O(string length)
public boolean isValid(String s)
{




      
      // Validate the input 
      if (s== null || s.length == 0)
          //return false;
          // NOTE: empty is always VALID pair
          return true





      LinkedList stack = new LinkedList();
      for (int i = 0 ; i < s.length(); i++) 
      {
           char c = s.charAt(i);
           switch(c)
           {
                case '(':
                case '[':
                case '{':
                    stack.push(c);
                    // NOTE: BREAK, don't want to go over below cases
                    break;
                case ')': 
                    //if (!stack.isEmpty())
                    //{
                    //    //char c2 = stack.pop();
                    //    // NOTE: Character
                    //    Character c2 = stack.pop();
                    //    // NOTE: Character equal http://www.tutorialspoint.com/java/lang/character_equals.htm
                    //    //return c2=='(';
                    //    return c2.equals('(');
                    //}
                    //else
                    //    return false;
                    // NOTE: even equal, need to iterate instead of return
                    if (stack.isEmpty() || stack.pop() != '(' )
                          return false;
                    break;
                case ']':
                    //if (!stack.isEmpty())
                    //{
                    //    //char c2 = stack.pop();
                    //    // NOTE: Character
                    //    Character c2 = stack.pop();
                    //    return c2=='[';
                    //    
                    //}
                    //else 
                    //    return false;
                    if ( stack.isEmpty() || stack.pop() != '[' )
                          return false;
                    break;
                case '}':
                    //if (!stack.isEmpty())
                    //{
                    //   Character c2 = stack.pop();
                    //    return c2 == '{';
                    //}
                    //else 
                    //    return false;
                    if (stack.isEmpty() || stack.pop() != '{')
                          return false;
                    break;
                default:
                    break;
           }
      }

 



      if (stack.isEmpty())
         return true;





      // NOTE: Otherwise, FASLE
      return false;



       
}

3. Similar Ones
(M) Generate Parentheses
(H) Longest Valid Parentheses

[Add][Math] Add Binary

1. Example

a= "11"
b ="  1"
Return "100"


2. Implementation
Q1:MSB->LSB
A1: From the end(len-1) and add backward . Consider carry
Q1: carry =1?
A1: add one more character
Q1: Add one more character ?
A1: StringBuilder.append("1").reverse()


res.append(sum%2);


// NOTE: iterating aIndex--; bIndex--;


// NOTE: remain digits while( aIndex >= 0 ) { int sum = (int) (a.charAt(aIndex) - '0') + carry; carry = sum /2; res.append(sum); aIndex--; } while ( bIndex >= 0) { int sum = (int) ( b.charAt( bIndex)- '0') + carry; carry = sum /2; res.append(sum); bIndex--; }


if ( carry > 0) res.append(carry);


// NOTE: reverse() is for StringBuilder 
 return res.reverse().toString();

// time:O(max(m,n)), Space:O(n) stringbuilder
public String addBinary(String a, String b)
{
     


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

  


       StringBuilder res = new StringBuilder();
       int aIndex = a.length()-1;
       int bIndex = b.length()-1;
       int carry = 0;
       while (aIndex >=0 && bIndex >=0 )
       {
            int sum = (int) (a.charAt(aIndex)-'0') + (int) (b.charAt(bIndex) - '0') + carry;
            // NOTE: append data type int ,double, boolean..etc,http://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html
            //res.append( String.valuesOf(sum%2) );
            res.append(sum%2);
            carry = sum/2;
            // NOTE: iterating
            aIndex--;
            bIndex--;
       }






       // NOTE: remain digits
       while( aIndex >= 0 )
       {
            int sum = (int) (a.charAt(aIndex) - '0') + carry;
            carry = sum /2;
            res.append(sum); 
            aIndex--;
       }
       while ( bIndex >= 0)
       {
            int sum = (int) ( b.charAt( bIndex)- '0') + carry;
            carry = sum /2;
            res.append(sum);
            bIndex--;
       }





       //if (carry ==1 )
       //     res.append("1");
       if ( carry > 0)
              res.append(carry);




       
       //res.toString().reverse();
       // NOTE: reverse() is for StringBuilder
       return res.reverse().toString();




}

3. Similar ones
(M) Add Two Numbers
(M) Multiply Strings
(M) Plus One

ZigZag Conversion

1. Example

s= "PAYPALISHIRING"
Zigzag s :

P     A     H     N
A P L  S I   I  G
Y    I      R

|     |     |    |
|  /  |   / |  / |
|     |     |    |

|       |
|    /  |
|  /    |
|       |

2. Implementation

[0]     [4]    [8]       [12] -> row0   0+(numRows+numRows-2)=0+2numRows-2
[1][3][5][7][9][11][13]-> row 1   1+(numRows-row)=
[2]     [6]    [10]     [14]-> row 2   2+(numRows-2+numRows)=2+2numRows-2

[0]         [6]             [12]             [18]->row0= 0+ 2numRows-2
[1]    [5][7]       [11][13]      [17][19]->row1= numRows-1
[2][4]    [8][10]       [14][16]      [20]->row2=numRows-2
[3]         [9]             [15]             [21]->row3= 2+ 2numRows-2

row+4*i
row+(4-row*2)*i
row+4*i
// NOTE: general gap int size = 2*NumRows -2;
// NOTE: specific gap, general gap - 2*row index. bigger row index, closer the gap = gap- row*2 element per each row if (i != 0 && i != numRows-1 && j+size-2*i < s.length() ) res.append(s.charAt(j+size-2*i));

Time:O(n), Sapce:O(n)
public String convert(String s, int numRows)
{
     




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

      //if (numRows<=0)
      //     return s;
      if (s == null || s.length() == 0 || numRows<=0 )
            return "";

      if (numRows ==1)
            return s;





      
      StringBuilder res = new StringBuilder();
      // NOTE: general gap
      int size = 2*NumRows -2;





      for (int i = 0; i < numRows; i-- )
      {
            //for (int j = 0; i < s.length();j++)
            for (int j = i; j < s.length(); j+=size)
            {



                res.append(s.charAt(j));
                //(i%2 ==0) ? res.add(s.charAt[i+(numRows+(numRows-2))*j]) : res.add(s.charAt[i+(4-i*2)*j]);



                // NOTE: specific gap, general gap - 2*row index. bigger row index, closer the gap = gap- row*2 element per each row
                if (i != 0 && i != numRows-1 && j+size-2*i < s.length() )
                res.append(s.charAt(j+size-2*i));
                

               
            }
      }




      return s.toString();

   

}

3. Similar Ones