Leetcode: 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)

NP问题。也是采用递归的解法。基本思路就是取出一个合法的数字，作为IP地址的一项，然后递归处理剩下的项。可以想象出一颗树，每个结点有三个可能的分支（因为范围是0-255，所以可以由一位两位或者三位组成）。并且这里树的层数不会超过四层，因为IP地址由四段组成，到了之后我们就没必要再递归下去，可以结束了。这里除了上述的结束条件外，另一个就是字符串读完了。

第二遍做法：

 1 public class Solution {
 2     public List<String> restoreIpAddresses(String s) {
 3         ArrayList<String> res = new ArrayList<String>();
 4         helper(res, "", s, 0, 1);
 5         return res;
 6     }
 7     
 8     public void helper(ArrayList<String> res, String item, String input, int index, int level) {
 9         if (level == 4) {
10             String str = input.substring(index);
11             if (isValid(str)) {
12                 item = item + "." + str;
13                 res.add(item);
14             }
15             return;
16         }
17         for (int i=index; i<index+3 && i<input.length(); i++) {
18             String str = input.substring(index, i+1);
19             if (isValid(str)) {
20                 if (item.length() == 0) {
21                     helper(res, str, input, i+1, level+1);
22                 }
23                 else {
24                     helper(res, item+"."+str, input, i+1, level+1);
25                 }
26             }
27         }
28     }
29     
30     public boolean isValid(String str) {
31         if (str==null || str.length()==0) return false;
32         if (str.length() > 3) return false;
33         if (str.charAt(0) == '0' && str.length() > 1) return false;
34         int value = Integer.parseInt(str);
35         if (value<0 || value>255) return false;
36         return true;
37     }
38 }

第一遍参考Code Ganker的做法，也不错

 1 public class Solution {
 2     public List<String> restoreIpAddresses(String s) {
 3         ArrayList<String> res = new ArrayList<String>();
 4         if (s == null || s.length() == 0) return res;
 5         helper(res, "", s, 1, 0);
 6         return res;
 7     }
 8     
 9     public void helper(ArrayList<String> res, String item, String s, int level, int index) {
10         if (index >= s.length()) return;
11         if (level == 4) {
12             String st = s.substring(index);
13             if (isValid(st)) {
14                 String f = String.format("%s.%s", item, st);
15                 res.add(f);
16             }
17             return;
18         }
19         for (int i=1; i<4&&(index+i<=s.length()); i++) {
20             String str = s.substring(index, index+i);
21             if (isValid(str)) {
22                 if (item.length() == 0) {
23                     helper(res, str, s, level+1, index+i);
24                 }
25                 else {
26                     String temp = String.format("%s.%s", item, str);
27                     helper(res, temp, s, level+1, index+i);
28                 }
29             }
30         }
31     }
32     
33     public boolean isValid(String str) {
34         if (str == null || str.length()>3) return false;
35         if (str.charAt(0) == '0' && str.length()>1) return false;
36         int num = Integer.parseInt(str);
37         if (num>=0 && num<=255) {
38             return true;
39         }
40         return false;
41     }
42 }