LeetCode 93. 复原 IP 地址

题目描述
一个有效的 IP 地址由四个介于 0 到 255 之间的整数组成，整数之间用点分隔，且不能包含前导零（例如，01 是无效的）。给定一个只包含数字的字符串 s，请你返回所有可能从 s 获得的有效 IP 地址。你可以以任意顺序返回答案。

示例：

输入：s = "25525511135"
输出：["255.255.11.135", "255.255.111.35"]
解释：两种可能的 IP 地址。

注意：s 的长度在 1 到 20 之间。

解题过程

第一步：理解问题核心

• IP 地址的格式：A.B.C.D，四段，每段是 0~255 的整数，且不能有前导零（除非这段就是 0 本身）。
• 我们需要将给定的数字字符串 s 切割成四段，每段对应一个整数，并满足上述规则。
• 这是一个组合分割问题，可以用深度优先搜索（回溯）解决。

第二步：设计回溯思路
我们从字符串起始位置开始，依次尝试截取 1 到 3 个字符作为一段，判断这段是否合法，如果合法则继续递归截取下一段，直到分成四段且用完所有字符。

回溯函数参数通常包括：

• start：当前在字符串 s 中开始截取的位置。
• path：当前已经形成的分段（列表形式）。
• result：保存所有合法 IP 地址的结果列表。

终止条件：

• 当已经分成四段（len(path) == 4），并且 start 恰好等于字符串长度时，说明找到一个合法 IP，将其加入结果。
• 如果分成了四段但还没用完字符，或者字符用完了但还不够四段，则直接返回。

第三步：判断一段是否合法的规则
设截取的子串为 segment：

1. 长度在 1 到 3 之间（因为 IP 每段最多 3 位数字）。
2. 如果 segment[0] == '0'，那么该段长度必须为 1（即只能是 "0"），否则就是前导零无效。
3. 将该段转换成整数 num，必须满足 0 <= num <= 255。

第四步：回溯过程详解
以 s = "25525511135" 为例，我们模拟初始几步：

1. 从 start = 0 开始，尝试截取长度 1、2、3：
   • 截取 "2"，合法，path = ["2"]，递归进入下一段。
   • 在第二段从 start = 1 开始，再尝试截取…
   • 如此递归，直到四段。

需要注意：每段最多截取 3 个字符，且剩余字符长度必须足够组成剩余段数（每段至少 1 个字符）。例如，在已有两段后，剩余字符数必须至少为 4 - len(path)。

第五步：代码框架（Python）

class Solution:
    def restoreIpAddresses(self, s: str):
        result = []
        
        def valid(segment):
            # 规则判断
            if len(segment) > 1 and segment[0] == '0':
                return False
            num = int(segment)
            return 0 <= num <= 255
        
        def backtrack(start, path):
            if len(path) == 4:
                if start == len(s):
                    result.append('.'.join(path))
                return
            # 尝试截取 1~3 个字符
            for length in range(1, 4):
                if start + length > len(s):
                    break
                segment = s[start:start+length]
                if valid(segment):
                    path.append(segment)
                    backtrack(start+length, path)
                    path.pop()  # 回溯
        
        backtrack(0, [])
        return result

第六步：复杂度分析

• 时间复杂度：由于 IP 地址固定四段，每段最多 3 种长度选择，理论上最多尝试 3^4 = 81 种组合，但在回溯中会提前剪枝，因此实际复杂度远小于 O(3^4 * n)，可以视为 O(1) 因为 n ≤ 20 且组合有限。
• 空间复杂度：O(n) 用于存储路径和递归栈。

第七步：关键点总结

1. 回溯剪枝：在递归中，如果剩余字符太多或太少，可以提前退出（虽然上述代码通过 start+length > len(s) 和最后 len(path)==4 判断，也可以显式加入剩余长度检查加速）。
2. 前导零处理："0" 合法，"01" 不合法。
3. 字符串转整数范围：必须在 0~255 之间。

最终：通过回溯，我们枚举所有可能的分割方式，并筛选出符合 IP 地址规则的组合，即可得到所有有效 IP 地址。