描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

链接

93. 复原 IP 地址 - 力扣（LeetCode） (leetcode-cn.com)

 

解法一：

 1 class Solution {
 2     List<String> res = new ArrayList<>();
 3     // Deque<Integer> path = new LinkedList<>();
 4 
 5     public List<String> restoreIpAddresses(String s) {
 6         if (s.length()<4 || s.length() >12) return res;
 7         BackTracking(s, 0, 0);
 8         return res;
 9     }
10 
11     public void BackTracking(String s, int index, int pointNums) {
12         // 此时，判断最后一段
13         if(pointNums == 3) {
14             if (isValid(s, index, s.length() - 1)) {
15                 res.add(s);
16             }
17             return;
18         }
19         for (int i = index; i < s.length(); i++) {
20             if (isValid(s, index, i)) {
21                 s = s.substring(0, i + 1) + '.' + s.substring(i + 1);
22                 pointNums++;
23                 BackTracking(s, i + 2, pointNums);
24                 pointNums--; // 回溯
25                 s = s.substring(0, i + 1) + s.substring(i + 2); // 回溯删掉逗点
26             }else {
27                 break; // 用else后break，相当于剪枝
28             }
29         }
30     }
31 
32     public boolean isValid(String s, int start, int end) { // 双指针判断
33         if (start > end) return false;
34         int len = end - start + 1;
35         //当前为0开头的且长度大于1的数字需要剪枝
36         if (len > 1 && s.charAt(start) == '0') {
37             return false;
38         }
39         //将当前截取的字符串转化成数字
40         int JudgeNum = len <= 0? 0 : Integer.parseInt(s.substring(start,end + 1));
41         //判断截取到的数字是否符合
42         return JudgeNum >= 0 && JudgeNum <= 255;
43     }
44 }

 

解法二：

 1 class Solution {
 2 
 3     List<String> res = new ArrayList<>();
 4     Deque<String> path = new ArrayDeque<>(4);
 5     String s;
 6     public List<String> restoreIpAddresses(String s) {
 7         this.s = s;
 8         dfs(0, 4);
 9         return res;
10     }
11     //剔除一些不变量，最后只保留当前索引和剩余段数
12     public void dfs(int begin, int reside){
13         if(begin == s.length()){
14             //当遍历到最后一个字符且剩余段数为0时，将此时的path添加到结果中
15             if(reside==0){
16                 res.add(String.join(".", path));
17             }
18             return;
19         }
20         //每段最多只截取3个数
21         for(int i=begin; i<begin+3; i++){
22             if(i >= s.length())
23                 break;
24             //字符串剩余长度和分段所需长度
25             if(s.length()-i > reside*3)
26                 continue;
27             //当截取的字符串满足条件
28             if(judgeNumber(s, begin, i)){
29                 String curS = s.substring(begin, i+1);
30                 path.addLast(curS);
31                 dfs(i+1, reside-1);
32                 path.removeLast();
33             }
34         }
35     }
36 
37     public boolean judgeNumber(String s, int left, int right){
38         int len = right - left + 1; 
39         //当前为0开头的且长度大于1的数字需要剪枝
40         if(len>1 && s.charAt(left)=='0')
41             return false;
42         //将当前截取的字符串转化成数字
43         int res = len<=0 ? 0 : Integer.parseInt(s.substring(left, right+1));
44         //判断截取到的数字是否符合
45         return res>=0 && res<=255;
46     }
47 }

 

参考

carl