尘雨尘风

数学与编程的爱好者

0%

leetcode题解93：复原IP地址

发表于 分类于
本文字数： 790 阅读时长 ≈ 1 分钟

描述

该题来自于力扣第93题

分析

很明显可以看出又是一个大问题逐渐化解成相似的小问题的解法，要找出3个切割点，可以先找出第一个切割点，然后剩余的字符串中找出其他2个切割点，所以该题解法本质是深度优先遍历的递归解法。

具体方法：
1. 找出所有符合条件的第一个切割点；
2. 遍历所有切割点，获取剩下的字符串，继续1直到字符串为空，表示切割完成；如果字符串不为空，表示切割失败。

理解了上述过程，其余部分就简单了，具体看代码。

代码

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
class Solution:
    def find_dots(self, s):
        dots = []
        for i in range(1, len(s)+1):
            if i == 1:
                dots.append(i)
            if i == 2 and s[0] != '0':
                dots.append(i)
            if i == 3 and ("100" <= s[:3] <= "255"):
                dots.append(i)
        return dots

    def restore(self, s, n):
        ans = []
        if n == 0:
            if len(s) == 0:
                ans.append("")
            return ans
        dots = self.find_dots(s)
        for dot in dots:
            subans = self.restore(s[dot:], n-1)
            for sub in subans:
                if sub == "":
                    ans.append(s[:dot])
                else:
                    ans.append(s[:dot] + "." + sub)
        return ans

    def restoreIpAddresses(self, s: str) -> List[str]:
        return self.restore(s, 4)
相关文章