[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...