Leetcode 剑指 Offer II 087.复原 IP 地址

题目难度: 中等

原题链接

今天继续更新 ******** 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 IP 地址。你可以按任何顺序返回答案。

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

提示：

0 <= s.length <= 3000
s 仅由数字组成

题目思考

如何尽可能优化时间复杂度?

解决方案

分析题目, 既然有效 IP 地址恰好有 4 段, 我们可以从头开始构造每一段, 直到达到字符串结尾, 或者段数达到 4
这就是典型递归回溯的思路, 具体如下:
1. 记录当前段起始下标 start (初始化为 0), 以及当前已经分好的 IP 段 path (初始化为空列表)
2. 然后遍历当前段终点 end, 其取值范围是[start, min(n,start+3)) (左闭右开区间), 因为每一段最大值是 255, 对应字符串长度最多为 3
3. 在遍历过程中, 动态更新当前段对应的数字 num (num=num*10+int(s[end])), 如果它大于 255 就 break, 无法构成有效 IP
4. 另外如果 start 对应字符是 0, 那么当 end 大于 start 时也要 break, 因为前导 0 无效
5. 如果不是上述两种情况, 则说明找到一个有效的 num, 将其字符串加入 path 中, 然后从 end+1 开始继续递归
6. 最终当 start 达到 n 或 path 长度达到 4 时, 说明达到递归出口, 此时必须两者同时满足才说明构造了一个有效的 IP 地址, 才将其加入最终结果
下面的代码中有详细的注释, 方便大家理解

复杂度

时间复杂度 O(3^4): 对于递归部分, IP 地址共有 4 段, 每段最多考虑 3 种情况, 所以这部分时间复杂度是 O(3^4), 而构造有效 path 的时间复杂度是 O(C) (C=min(len(s),16)), 所以综合复杂度就是 O((3^4)*C)
空间复杂度 O(1): 递归栈的最大深度是 4, 而 path 数组存储的字符个数最多是 16, 都是常数, 所以空间复杂度是 O(1)

代码

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # 回溯+传下标和当前数组+转数字判断
        # 传入当前下标和当前ip数组, 判断以当前下标为起点长度为1~3的字符串是否<=255
        n = len(s)
        res = []

        def dfs(start, path):
            if start == n or len(path) == 4:
                # 递归出口, 下标达到末尾或者ip数组长度已经达到4
                if start == n and len(path) == 4:
                    # 只有两者同时满足时才是有效的ip地址
                    res.append(".".join(path))
                return
            num = 0
            for end in range(start, min(n, start + 3)):
                if end > start and s[start] == "0":
                    # 前导0, 直接break
                    break
                num = 10 * num + int(s[end])
                if num > 255:
                    # 当前数字已经超过255了, 直接break
                    break
                # 将当前数字追加到path中, 然后以end+1作为起点继续递归
                dfs(end + 1, path + [str(num)])

        dfs(0, [])
        return list(res)