【Leetcode】93.复原IP地址

93.复原IP地址

题目

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

有效的 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 地址。

 

示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：
输入：s = "1111"
输出：["1.1.1.1"]

示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

方法（暴力法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<String>();
    if(s == null || s.length() == 0 || s.length() > 12)
        return res;
    StringBuffer ip = new StringBuffer();
    for(int a = 1; a < 4; a++){
        for(int b = a + 1; b < a + 4; b++){
            for(int c = b + 1; c < s.length(); c++){
                int n1 = Integer.parseInt(s.substring(0, a));
                int n2 = Integer.parseInt(s.substring(a, b));
                int n3 = Integer.parseInt(s.substring(b, c));
                int n4 = Integer.parseInt(s.substring(c, s.length()));
                if(n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255)
                    ip.append(n1).append(".").append(n2).append(".").append(n3).append(".").append(n4);
                if(ip.length() == s.length() + 3)
                    res.add(ip.toString());
                ip.delete(0, ip.length());
            }
        }
    }
    return res;
}

方法（回溯法）

  • 递归终止条件：当遍历完S的每一位时，如果已经切分好了IP地址的四段，那么将切分好的IP地址加入结果。否则直接返回。
  • 选择：在每一个位置都有三种选择：截取当前位置和后1位作为IP地址中的一段、截取当前位置和后2位作为IP地址中的一段、截取当前位置和后3位作为IP地址中的一段
  • 路径：用一个列表记录分割成的IP地址的每一段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
List<String> res;
String s;
public List<String> restoreIpAddresses(String s) {
    this.s = s;
    res = new LinkedList<>();
    if(s.length() > 12 || s.length() < 4)
        return res;
    List<String> path = new LinkedList<>();
    backtrack(0, 0, path);
    return res;
}
//start代表从哪个位置开始回溯
//cutNum代表已经分割了IP地址中的多少段（最多为4段）
//path记录当前分割成的IP地址中的每一段
public void backtrack(int start, int cutNum, List<String> path){
    //终止条件
    if(start == s.length()){
        if(cutNum == 4)
            res.add(String.join(".", path));
    }
    //在每一个结点处可以选择截取的方法只有 3 种：向后截 1 位、截 2 位、截 3 位
    for(int i = start; i < start + 3; i++){
        //一下两个if判断为剪枝条件
        if(i > s.length())
            break;
        if((4 - cutNum) * 3 < s.length() - i)
            continue;
        if(validIPsegment(start, i)){
            String temp = s.substring(start, i + 1);
            path.add(temp);
            backtrack(i + 1, cutNum + 1, path);
            path.remove(path.size() - 1);
        }
    }
}
//判断S中从left到right中间的部分是否是合法的IP地址段
public boolean validIPsegment(int left, int right){
    if((left < right && s.charAt(left) == '0') || right >= s.length())
        return false;
    int count = 0;
    for(int i = left; i <= right; i++){
        count = count * 10 + (s.charAt(i) - '0');
    }
    return count >= 0 && count <= 255;
}

参考