93. Restore IP Addresses Leetcode Java

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

Typical recursion problem.

There are totally 4 sections.The length of the string must be between 4 an 12.

The base case/ terminating case:

section>4 and the starting index>=String.length, which means, when we finish 4th section, there is no more unprocessed chars left in the string.

Recursion step:

process it section by section rather than char by char, try current section with one char,two chars, then three chars, and there are several restriction for each section:

First of all, the number of each section must be <=255, secondly, if the first digit is 0, then the current section must be 0, so no 00 or 000. 

Some other small tips: where to add '.', also remember to delete '.' when backtrack to current section. 

 public List<String> restoreIpAddresses(String s) {  
    List<String> res=new ArrayList<String>();  
    if(s==null || s.length()<4 || s.length()>12) return res;  
    StringBuilder sb=new StringBuilder();  
    helper(0,s,1,sb,res);  
    return res;  
   }  
   public void helper(int start, String s, int section, StringBuilder sb, List<String> res){  
     if(section>4){  
       if(start>=s.length()) res.add(sb.toString());  
       return;  
     }  
     if(start>=s.length()) return;  
     int maxNum=(s.charAt(start)=='0')? 1:3;  
     for(int i=start;i<s.length() && i<start+maxNum; i++){  
       if(Integer.parseInt(s.substring(start,i+1))<=255){  
         if(section>1) sb.append('.');  
         sb.append(s.substring(start,i+1));  
         helper(i+1,s,section+1,sb,res);  
         sb.delete(sb.length()-(i+1-start),sb.length());  
         if(section>1) sb.deleteCharAt(sb.length()-1);  
       }  
     }  
   }