Leetcode 93 Restore IP Addresses

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 1: iterative

 public class Solution {  
   public List<String> restoreIpAddresses(String s) {  
     int n=s.length();  
     List<String> res=new ArrayList<>();  
     for (int i=1; i<=3 ; i++) {  
       if (i<n-9) continue;  
       for (int j=i+1; j<=i+3; j++) {  
         if (j<n-6) continue;  
         for (int k=j+1; k<=j+3 && k<n; k++) {  
           if (k<n-3) continue;  
           int a=Integer.valueOf(s.substring(0,i));  
           int b=Integer.valueOf(s.substring(i,j));  
           int c=Integer.valueOf(s.substring(j,k));  
           int d=Integer.valueOf(s.substring(k,n));  
           if (a>255 || b>255 || c>255 || d>255) continue;  
           String one=String.valueOf(a)+'.'+String.valueOf(b)+'.'+String.valueOf(c)+'.'+String.valueOf(d);  
           if (one.length()<n+3) continue;  
           res.add(one);  
         }  
       }  
     }  
     return res;  
   }  
 }  

Solution 2: recursive

 public class Solution {  
   public List<String> restoreIpAddresses(String s) {  
     List<String> res=new ArrayList<>();  
     dfs(0,s,"",res);  
     return res;  
   }  
   private void dfs(int d, String s, String one, List<String> res) {  
     int n=s.length();  
     if (d==4) {  
       if (n==0) res.add(one.substring(0,one.length()-1));  
     }  
     else {  
       if (n>=1) dfs(d+1,s.substring(1),one+s.charAt(0)+'.',res);  
       if (n>=2 && s.charAt(0)!='0') dfs(d+1,s.substring(2),one+s.substring(0,2)+'.',res);  
       if (n>=3 && s.charAt(0)!='0') {  
         String t=s.substring(0,3);  
         if (Integer.valueOf(t)<=255) dfs(d+1,s.substring(3),one+t+'.',res);  
       }  
     }  
   }  
 }