93. Restore IP Addresses java solutions

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)

 1 public class Solution {
 2     public List<String> restoreIpAddresses(String s) {
 3         List<String> ans = new ArrayList<String>();
 4         if(s.length() < 4 || s.length() > 12)
 5             return ans;
 6         recursive(ans,0,s,"");
 7         return ans;
 8     }
 9     
10     public void recursive(List<String> ans, int s, String str, String tmp){
11         if(s == 3 && check(str)){// 其实取到第三层之后，判断剩下的是否合法，第四层就不用再递归了。
12             ans.add(new String(tmp+str));
13             return;
14         }
15         for(int i=0; i<3 && i<str.length()-1; i++){
16             String substr = str.substring(0,i+1);
17             if(check(substr)){
18                 recursive(ans,s+1,str.substring(i+1,str.length()),tmp+substr+".");
19             }
20         }
21     }
22     
23     public boolean check(String substr){
24         if(substr.charAt(0) == '0')
25             return "0".equals(substr);
26         int num = Integer.parseInt(substr);
27         if(num > 255 || num < 1) return false;
28         return true;
29     }
30 }

这一题做的很艰难，边界条件不好界定。

几点注意的地方：

1. 在验证字符串是否是数字的时候，要注意0的情况，001，010，03都是非法的。所以，如果第一位取出来是0，那么我们就判断字符串是否是"0"，不是的情况都是非法的

2. 取字符串的时候，注意位数不够的问题，不仅<3, 而且<s.length()-1

3. 注意substring的范围

4. 字符串转换成数字 Integer.parseInt();

5. 别忘了IP 地址里面的 "."