Leetcode 90

Posted on | | 阅读数
Words count in article: 279 | Reading time ≈ 1

Question

Solution

首先，IP的地址格式是XXX.XXX.XXX.XXX，其中XXX是不大于255的数。去除s长度大于12的情况。

其次，我们总共可以切割4次，且切完之后s没有剩余。如果切割次数超过4次，直接舍去。

分类讨论。

如果取一位数，直接符合条件。

如果取两位数，那么需要考虑到一种特殊情况，即第一位为0，这种情况不符合要求。

如果取三位数，首先要满足第一位不为0，并且这个三位数要小于等于255。

现在可以考虑使用dfs来解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        if not s or len(s) < 4 or len(s) > 12:
            return []
        results = []
        self.dfs(0, s, "", results)
        return results
    
    def dfs(self, times, s, temp, results):
        if times == 4:
            if not s:
                results.append(temp[1:])
                return
        if times > 4:
            return 
        for i in range(1, 4):
            if i <= len(s):
                if i == 1:
                    self.dfs(times+1, s[i:], temp+"."+s[:i], results)
                elif i == 2 and s[0] != "0":
                    self.dfs(times+1, s[i:], temp+"."+s[:i], results)
                elif i == 3 and s[0] != "0" and int(s[:3]) <= 255:
                    self.dfs(times+1, s[i:], temp+"."+s[:i], results)