0093. 复原 IP 地址

0093. 复原 IP 地址 #

  • 标签:字符串、回溯
  • 难度:中等

题目大意 #

给定一个只包含数字的字符串,用来表示一个 IP 地址,返回所有由 s 构成的有效 IP 地址,可以按任何顺序返回答案。

  • 有效 IP 地址:正好由四个整数(每个整数由 0~255 的数构成,且不能含有前导 0),整数之间用 . 分割。

例如:0.1.2.201192.168.1.1 是有效 IP 地址,但是 0.011.255.245192.168.1.312192.168@1.1 是 无效 IP 地址。

解题思路 #

回溯算法。使用 res 存储所有有效 IP 地址。用 point_num 表示当前 IP 地址的 . 符号个数。

定义回溯方法,从 start_index 位置开始遍历字符串。

  • 如果字符串中添加的 . 符号数量为 3,则判断当前字符串是否为有效 IP 地址,若为有效 IP 地址则加入到 res 数组中。直接返回。
  • 然后在 [start_index, len(s) - 1] 范围循环遍历,判断 [start_index, i] 范围所代表的子串是否合法。如果合法:-
    • 则 point_num + 1。
    • 然后在 i 位置后边增加 . 符号,继续回溯遍历。
    • 最后 point_num - 1 进行回退。
  • 不符合则直接跳出循环。
  • 最后返回 res。

代码 #

 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
class Solution:
    res = []
    def backstrack(self, s: str, start_index: int, point_num: int):
        if point_num == 3:
            if self.isValid(s, start_index, len(s) - 1):
                self.res.append(s)
            return
        for i in range(start_index, len(s)):
            if self.isValid(s, start_index, i):
                point_num += 1
                self.backstrack(s[:i+1] + '.' + s[i+1:], i + 2, point_num)
                point_num -= 1
            else:
                break

    def isValid(self, s: str, start: int, end: int):
        if start > end:
            return False
        if s[start] == '0' and start != end:
            return False
        num = 0
        for i in range(start, end + 1):
            if s[i] > '9' or s[i] < '0':
                return False
            num = num * 10 + ord(s[i]) - ord('0')
            if num > 255:
                return False
        return True

    def restoreIpAddresses(self, s: str) -> List[str]:
        self.res.clear()
        if len(s) > 12:
            return self.res
        self.backstrack(s, 0, 0)
        return self.res
本站总访问量  次  |  您是本站第  位访问者