「脸书」刷题决定前途 93 ～ 修复 IP 地址

基本信息

• 题号：93
• 题厂：脸书
• 难度系数：中

已知一个一个字符串，返回这个字符串可能组成的 ip 地址……

例如 s = "25525511135"
返回 ["255.255.11.135","255.255.111.35"]，即可能的 ip 有 255.255.11.135 或 255.255.111.35

解题思路

• 找有效组合的题 === backtracking
• 明白需要用 backtracking 后，再联想 backtracking 模板——怎么弄一个 recursive 方法
• 本题有效的 ip 地址为 4 段，每一段的取值范围 0 ～ 255。这里要特别注意 0：如果是 2 位数和 3 位数，0 不能开头，即 01 不可行，010 也不可行……同时，我们需要把字符串所有字符全部用于分配……

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []

        # IP 地址最大值 255.255.255.255，最多 12 位……
        # 当字符串长度大于 12 时，是不可能分割成有效 4 段 IP 地址……
        if len(s) > 12:
            return res
            
        def backtrack(i, dots, cur):
            # 当完成 4 段分割且长度和 s 相等时，说明这是一个有效的 ip 地址，添加进返回结果……
            if dots == 4 and i == len(s):
                res.append(cur[:-1])
                return
            # 如果有超过 4 段，则无效……返回但不添加……
            if dots > 4:
                return
            
            # 循环时，除了当前字段小于 256 之外，还要满足 0 不能开头。0 开头的情况只能是 0。。。。
            for j in range(i, min(i + 3, len(s))):
                if int(s[i: j + 1]) < 256 and (i == j or s[i] != "0"):
                    backtrack(j + 1, dots + 1, cur + s[i:j + 1] + ".")
            
        backtrack(0, 0, "")

        return res

Constraints

• 1 <= s.length <= 20
• s consists of digits only.

测试

• 0， 255，256……边界测试
• 101，10， 01……可能 0 开头的的情况测试
• ……

Big O

• 时间复杂度：O（3^n）最坏的情况是一直出现 255 这样的有效 3 位数，一直做 3 重循环……
• 空间复杂度：O（1）或 O（4），因为最多只有 4 段……

总结

• 本题除了考察 backtracking，还顺带复习了 ipv4
• 考试时如果为了 ipv4 格式和考官讨论，就……又……歇菜了……