LeetCode 93. 复原IP地址（中）

这个题要一个字符一个字符的截取，所以关键是要想清楚有哪些剪枝条件，以用来缩小解空间。

题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
Given a string containing only digits, restore it by returning all possible valid IP address combinations.

示例

示例: 

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

考察知识点

回溯算法

核心思想

方法一、回溯算法
直觉
IP地址由32位二进制数组成，为便于使用，常以 XXX.XXX.XXX.XXX 形式表现，每组 XXX 代表小于或等于255的10进制数。
所以说IP地址总共有四段，每一段可能有一位，两位或者三位，范围是[0, 255]。
题目明确指出输入字符串只含有数字，所以当某段是三位时，我们要判断其是否越界（>255)。
还有一点很重要的是，当只有一位时，0可以成某一段，如果有两位或三位时，像 00， 01， 001， 011， 000等都是不合法的。

剪枝 由以上条件可知，我们有以下几种需要剪枝的情况
1. P地址总共有四段，由于最大地址不过 255，所以单次截取的字符串的长度不能超过3，超过3就可以剪枝了。 if len(clip_s) > 3: break 2. 前方法截取字符串之后，剩余的字符个数不能过多，例如还有三个ip段需要确定，最多需要 \(3 \times 3\) 也就是9个字符，但是按照当前方法截取之后还剩10个字符，就可以剪枝了（当确定最后一个ip段时，可以不考虑这个剪枝条件）。if depth !=3 and len(s[i:]) > (4 - depth - 1) * 3: continue 3. 截取出来的字符如果是三位数字且大于255，也需要剪枝。if len(clip_s) == 3 and int(clip_s) > 255: continue
4. 如果有两位或三位时，像 00， 01， 001， 011， 000 等都是不合法的。len(clip_s) > 1 and clip_s[0] == "0": continue
5. 如果是确定最后一个ip段，那么截取的就应该是全部剩余字符，否则 i自增，继续截取，直到截取完所有剩余字符之后再判断是否添加。if depth == 3 and clip_s != s: continue

b581bdde1cef982f0af3182af17fc3c41960c76a7445af0dcfd445c89b4c2eaa-「力扣」第 93 题：复原 IP 地址-1.png

Python版本

  • 方法一回溯法的实现
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# backtrak()为内部匿名函数的形式
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(s, path =  [], depth = 0 ):
            if depth == 4:
                res.append(".".join(path))
                return
            for i in range(1, len(s)+1):
                clip_s = s[:i]
                # 剪枝
                if len(clip_s) > 3:  # 最基本条件放在最前面，因为IP地址总共有四段，由于最大地址不过 255，所以clip_s的长度不能超过3。
                    break
                if depth == 3 and clip_s != s:
                    continue
                if depth !=3 and len(s[i:]) > (4 - depth - 1) * 3:  # 到最后一层之前都要考虑这个剪枝条件。
                    continue
                if  int(clip_s) > 255:
                    continue
                if len(clip_s) > 1 and clip_s[0] == "0":
                    continue
                # 选择
                path.append(clip_s)
                # 回溯
                backtrack(s[i:], path, depth+1)  # start+i这里不能加i
                # 撤销选择
                path.pop()
        res = []
        backtrack(s)
        return res


# backtrak()为外部函数的形式
class Solution:
    # 回溯函数
    def backtrack(self, s = "", path =  [], depth = 0, res = []):
        if depth == 4:
            res.append(".".join(path))
        else:
            for i in range(1, len(s)+1):
                clip_s = s[:i]
                pruning_result = self.pruning(clip_s, s, i, depth)  # 剪枝
                if pruning_result == 0:
                    break
                if pruning_result == -1:
                    continue
                path.append(clip_s)  # 选择
                self.backtrack(s[i:], path, depth + 1, res)  # 回溯
                path.pop()  # 撤销选择

    # 剪枝函数
    def pruning(self, clip_s, s, i, depth):
        if len(clip_s) > 3:  return 0
        if depth == 3 and clip_s != s:  return -1  # continue
        if depth !=3 and len(s[i:]) > (4 - depth - 1) * 3:  return -1  # continue
        if  int(clip_s) > 255:  return -1  # continuereturn -1  # continue
        if len(clip_s) > 1 and clip_s[0] == "0":  return -1  # continue
        return 1  # go on

    def restoreIpAddresses(self, s: str) -> List[str]:
        # 特判
        size = len(s)
        if size < 4 or size > 12:
            return []
        path = []
        res = []
        self.backtrack(s, path, 0, res)
        return res

Input = ["25525511135"]
Answer = [["255.255.11.135", "255.255.111.35"]]
if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        result = solution.restoreIpAddresses(Input[i])
        print(result == Answer[i])

liweiwei1419大佬的版本，更加简洁

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
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        size = len(s)
        if size < 4 or size > 12:
            return []
        path = []
        res = []
        self.__dfs(s, size, 0, 0, path, res)
        return res

    def __dfs(self, s, size, split_times, begin, path, res):
        if begin == size:
            if split_times == 4:
                res.append('.'.join(path))
            return
        if size - begin < (4 - split_times) or size - begin > 3 * (4 - split_times):
            return

        for i in range(3):
            if begin + i >= size:
                break
            ip_segment = self.__judge_if_ip_segment(s, begin, begin + i)
            if ip_segment != -1:
                path.append(str(ip_segment))
                self.__dfs(s, size, split_times + 1, begin + i + 1, path, res)
                path.pop()

    # 专门写了一个负责剪枝的函数
    def __judge_if_ip_segment(self, s, left, right):
        size = right - left + 1
        if size > 1 and s[left] == '0':
            return -1
        res = 0
        for i in range(left, right + 1):
            res = res * 10 + ord(s[i]) - ord('0')
        if res > 255:
            return - 1
        return res

时间复杂度 : 如上文所述，需要检查的组合不多于27个。
空间复杂度 : 常数空间存储解，不多于19 个有效IP地址。

3baa385fecae6239495c19c88a279f4b76752a7a089fabdf15685e829b8e0a73-image.png

有效语法糖

1、Python中字符串、list的截取位置的起止关系。
如果是从第 i 位开始往后面截取，那么第 i 位是不包含在截取结果中的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>> a = '25525511135'
>>> b = list('25525511135')
>>> a
'25525511135'
>>> b
['2', '5', '5', '2', '5', '5', '1', '1', '1', '3', '5']
>>> i = 1
>>> a[i:]
'5525511135'
>>> b[i:]
['5', '5', '2', '5', '5', '1', '1', '1', '3', '5']
>>> len(a)
11
>>> len(b)
11
>>> len(a[i:])
10
>>> len(b[i:])
10

参考链接

liweiwei1419题解
LeetCode官方题解