93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1 class Solution {
 2     private void helper(String s, int i,int cnt, List<Integer> res,List<String> result) {
 3         if (cnt == 4) {
 4             String s1 = s.substring(0,res.get(0));
 5             String s2 = s.substring(res.get(0), res.get(1));
 6             String s3 = s.substring(res.get(1), res.get(2));
 7             String s4 = s.substring(res.get(2), s.length());
 8             if (Integer.parseInt(s4) <= 255 && s4.length() <= Integer.toString(Integer.parseInt(s4)).length())
 9                 result.add(Integer.parseInt(s1)+"."+Integer.parseInt(s2)+"."+Integer.parseInt(s3)+"."+Integer.parseInt(s4));
10             return ;
11         }
12 
13         for (int j = i+1; j < s.length(); j++) {
14             // 判断划分是否合理
15             String s0 = s.substring(i,j);
16             int i1 = Integer.parseInt(s0);
17             if (i1 > 255)
18                 break;
19             if (s.length() - j > (3-cnt+1)*3)
20                 continue;
21             if (s0.length() > Integer.toString(i1).length()) {
22                 break;
23             }
24 
25             res.add(j);
26             helper(s, j, cnt+1, res, result);
27             res.remove(res.size()-1);
28         }
29     }
30 
31     public List<String> restoreIpAddresses(String s) {
32         List<Integer> res = new ArrayList<>();
33         List<String> result = new ArrayList<>();
34         // 首次划分(第一个小数点的位置)
35         for (int i = 1; i < s.length(); i++) {
36             String s0 = s.substring(0, i);
37             int i1 = Integer.parseInt(s0);
38             if (i1 > 255)
39                 break;
40             if (s.length() - i > 3*3)
41                 continue;
42             if (s0.length() > Integer.toString(i1).length()) {
43                 break;
44             }
45             res.add(i);
46             helper(s, i, 2, res, result);
47             res.remove(res.size()-1);
48         }
49         return result;
50     }
51 }