93. 复原 IP 地址 - Restore IP Addresses

🎯 问题描述（来源于LeetCode）

描述：
给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址（IPv4）。
有效 IP 地址由四个整数（每个在 0 到 255 之间）组成，且整数之间用 '.' 分隔。
不能包含前导零（例如 01 无效），但整数 0 本身是有效的。

说明：

字符串 s 的长度在 1 到 20 之间。
需要枚举所有可能的分割方式，返回所有有效的 IP 地址。

示例：

示例 1：

1 2	输入: s = "25525511135" 输出: ["255.255.11.135","255.255.111.35"]

示例 2：

1 2	输入: s = "0000" 输出: ["0.0.0.0"]

示例 3：

1 2	输入: s = "101023" 输出: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

💻 解题思路

思路：回溯法（DFS）枚举分段

算法步骤

获取字符串长度 n，初始化结果列表 ans 和路径列表 path（存储已确定的 IP 段）。
定义递归函数 dfs(i, cur)，其中 i 表示当前扫描到的下标，cur 表示当前正在累积的段（尚未决定切分）：
- 如果 i == n（扫描完所有字符）：
  - 如果 cur 非空（还有未切分的段），则将该段转为数字 x，检查是否有效（无前导零且范围 0-255）。若有效，则将其加入 path；若此时 path 长度正好为 4，则拼接成 IP 地址加入 ans；最后回溯弹出 path。
  - 如果 cur 为空（即没有剩余段），且 path 长度正好为 4，则直接拼接并加入 ans。
  - 返回。
- 否则，进行两个分支：
  - 不切分：将当前字符追加到 cur，递归 dfs(i+1, cur+s[i])。
  - 切分：如果 cur 非空，则检查 cur 表示的整数是否有效（规则同上），且当前 path 长度小于 4。若有效，则将 cur 加入 path，递归 dfs(i+1, s[i])（开始新段），然后回溯弹出。
从 dfs(0, "") 开始搜索。
返回 ans。

代码实现

from typing import List

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        n = len(s)
        ans = []
        path = []

        def dfs(i, cur):
            if i == n:
                if cur:
                    m = len(cur)
                    x = int(cur)
                    if (m == 1 and x == 0) or 255 >= x >= 10**(m-1):
                        path.append(cur)
                        if len(path) == 4:
                            st = ".".join(path)
                            ans.append(st)
                        path.pop()
                else:
                    if len(path) == 4:
                        st = ".".join(path)
                        ans.append(st)
                return

            # 不切分
            dfs(i+1, cur + s[i])

            # 切分
            if cur:
                m = len(cur)
                x = int(cur)
                if ((m == 1 and x == 0) or 255 >= x >= 10**(m-1)) and len(path) < 4:
                    path.append(cur)
                    dfs(i+1, s[i])
                    path.pop()

        dfs(0, "")
        return ans

📊 性能分析

时间复杂度：最坏情况下为 $O(3^4)$ 量级，实际上每个位置可切可不切，但通过有效性剪枝，通常远小于 $2^n$ 。对于长度 ≤ 20 的字符串，本解法在 LeetCode 上可通过。
空间复杂度： $O(n)$ ，递归栈深度和路径存储。

思考

该解法通过两个参数 (i, cur) 巧妙地模拟了 IP 地址的分段过程。cur 累积当前段的数字，递归中同时尝试“继续延长当前段”和“结束当前段并开启新段”两种分支。
优点：

直接模拟了 IP 地址的构造过程，逻辑完整。
对有效段的检查（前导零和范围）做了细致处理。

注意事项：

检查有效段的条件 (m == 1 and x == 0) or 255 >= x >= 10**(m-1) 能够正确处理 0（长度为1且值为0）以及非零数字（无前导零且 ≤ 255）。例如 "00" 会被判定无效，因为 m=2 且 10**(1)=10，0 不在 [10,255] 内，同时也不是 (m==1 and x==0)，因此正确。
递归中“切分”分支必须在 cur 非空时才能执行，避免了空段。
最终处理 i == n 时，需要同时处理 cur 非空（最后一段）和 cur 为空（已经切分完所有段）两种情况，并且对于 cur 为空的情况，只需检查 path 长度是否为 4。