一、背景

书接上回，招商银行“测试开发”社招笔试过了两天后，收到邮件、短信通知——笔试通过，进入面试流程，需选择面试时间。

14:30发的邮件选择面试时间，截止时间18:00，未选择视为放弃，所以面招商的宝子们，时不时看下自己的邮箱或短信，害怕错过啊...

可选面试时间只有第二天的下午、以及时间不合适，由于我第二天下午时间真的不合适，所以只能选了时间不合适。

等了一周都没有再收到邮件，我以为都凉了，每天都去招商招聘官网看自己的流程是否更新，一直都是面试中。

终于在第二周周五收到了邮件，赶紧选好面试时间。

其他问题还没有整理出来，先看编程题，在退出时，赶紧截图保存了下来：

左边是题目，右边写代码，提供这个平台的网站是牛客网，只给10分钟时间。

您猜怎么着，我盯着看了有5分钟左右，知道自己写不出来，说：面试官您好，不耽误您的时间，我写不出来，有大概方向，但要写出来可能会很复杂...

面试官：好，没关系，你可以说下思路

我：遍历、循环，不停判断

面试官：是循环，用什么循环

我：我会用递归（这个我掌握最差了，所以我看了半天，直接就说不会...）

面试官就没有再问了。

轻喷，确实没做出来...下来查答案，也不能说跟递归毫无关联...

二、完整题目

可能会看不清图片，完整题目描述是这样的：

现在有一个只包含数字的字符串，将该字符串转化成 IP 地址的形式，返回所有可能的情况。

示例：

输入: "25525522135"输出: ["255.255.22.135", "255.255.221.35"]（顺序没有关系）

数据范围：

• 字符串长度：0 < n ≤ 12

要求：

• 时间复杂度 O(n!)

• 空间复杂度 O(n!)

注意：ip 地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。

三、解题思路与考点

3.1 这道题在考什么？

3.2 什么是回溯算法？

生活中的例子：迷宫寻路

想象你在玩一个迷宫游戏，要找到出口：

入口 ─→ 遇到岔路口 ─→ 选左走 ─→ 死胡同！                              ↓                        退回去，换右边走 ─→ 找到出口！

这就是回溯的核心思想：

1. 尝试：做出一个选择

2. 失败：发现走不通

3. 回退：撤销选择，回到上一步

4. 再尝试：选择另一条路

3.3 本题的解题思路

把问题转换一下：在一个字符串中插入3个点，分成4段。

以 "25525522135" 为例：

原始字符串: 2 5 5 2 5 5 2 2 1 3 5            ↓ 在某些位置插入点可能的分割: 255.255.22.135           255.255.221.35

核心步骤：

第1步：尝试切分第1段（可以是1位、2位或3位数字）  第2步：对每种情况，继续尝试切分第2段 第3步：继续切分第3段和第4段  第4步：如果4段都合法且用完所有字符 → 找到一个答案！ 第5步：回退，尝试其他切分方式   

四、完整代码

实现：

from typing import Listclass Solution:def restoreIpAddresses(self, s: str) ->List[str]:self.result= []      # 存储所有找到的合法IP地址self.s=s# 将字符串保存为类属性，方便其他方法访问self.backtrack(0, [])  # 从位置0开始回溯return self.resultdef backtrack(self, start: int, parts: List[str]) ->None:"""        回溯函数：尝试所有可能的分割方式        Args:            start: 当前处理到的字符串位置（索引）            parts: 当前已经分割出的IP段列表        """# 情况1：已经分割出4段了if len(parts) ==4:# 如果字符串也刚好用完，说明找到一个合法IPif start==len(self.s):self.result.append('.'.join(parts))  # 用点连接4段，加入结果return# 无论是否找到，都返回（4段满了就不能继续分了）# 情况2：剪枝 - 提前判断不可能的情况remaining=len(self.s) -start# 剩余未处理的字符数segments_left=4-len(parts)        # 还需要分割几段# 如果剩余字符太少（不够每段1个）或太多（每段最多3个）if remaining<segments_left or remaining>segments_left*3:return# 直接放弃，不再继续尝试# 情况3：尝试切分1位、2位、3位数字for length in range(1, 4):  # length = 1, 2, 3# 边界检查：不能超出字符串长度if start+length>len(self.s):break# 已经到末尾了，退出循环# 取出这一段的字符segment=self.s[start:start+length]# 合法性检查# 规则1：如果有前导零（比如 "01"、"001"）不合法，但单独的 "0" 是合法的if length>1 and segment[0] =='0':continue# 跳过这种情况，尝试下一个长度# 规则2：数值不能超过255if int(segment) >255:continue# 跳过这种情况，尝试下一个长度# 这一段合法！递归处理剩余部分：parts + [segment] 创建一个新列表，加入当前这段self.backtrack(start+length, parts+ [segment])

咱也进行下测试，谁让我们是测试：

def test_restore_ip_addresses():"""测试函数"""test_cases= [# (输入字符串, 期望输出)        ("25525522135", ["255.255.22.135", "255.255.221.35"]),        ("0000", ["0.0.0.0"]),        ("101023", ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]),        ("010010", ["0.10.0.10", "0.100.1.0"]),        ("1111", ["1.1.1.1"]),        ("255255255255", ["255.255.255.255"]),        ("111", []),                    # 字符串太短，无法分割成4段        ("1111111111111", []),          # 字符串太长（>12）        ("", []),                        # 空字符串        ("256256256256", []),            # 所有段都>255        ("11111111",  ['1.1.111.111', '1.11.11.111', '1.11.111.11', '1.111.1.111', '1.111.11.11', '1.111.111.1', '11.1.11.111', '11.1.111.11', '11.11.1.111', '11.11.11.11', '11.11.111.1', '11.111.1.11', '11.111.11.1', '111.1.1.111', '111.1.11.11', '111.1.111.1', '111.11.1.11', '111.11.11.1', '111.111.1.1']),  # 8个1    ]solution=Solution()passed=0for i, (s, expected) in enumerate(test_cases, 1):result=solution.restoreIpAddresses(s)# 由于顺序不重要，使用集合比较is_pass=set(result) ==set(expected)status="✅ PASS"ifis_passelse"❌ FAIL"if is_pass:passed+=1print(f"\n测试用例 {i}:")print(f"  输入:   \"{s}\"")print(f"  期望:   {expected}")print(f"  实际:   {result}")print(f"  状态:   {status}")print("\n"+"="*60)print(f"总计: {passed}/{len(test_cases)} 通过")print("="*60)

部分测试结果：

五、代码关键点分析

5.1 关键变量解析

5.2 两个重要的判断条件

条件1：前导零判断

if length>1 and segment[0] =='0':continue

条件2：数值范围判断

if int(segment) >255:continue

5.3 剪枝优化是什么？

"剪枝" 就是在搜索树上剪掉不可能的分支，避免浪费时间。

假设还剩 2 个字符，还需要分 3 段：- 每段至少1个字符 → 最少需要 3 个字符- 现在只有 2 个 → 不可能成功！- 直接放弃，不再继续尝试这就是"剪枝"——提前发现不可能，及时止损

剪枝条件表：

六、实现逻辑

6.1 具体例子演示：以 "25525522135" 为例

让我们一步步看代码是如何找到答案的：

字符串: "25525522135" (长度11)        索引: 0123456789...目标: 找到所有合法的 IP 地址

搜索过程可视化：

第1次尝试（第1段取"2"）:├── 第1段: "2" ✅│   ├── 第2段: "5" ✅│   │   ├── 第3段: "5" ✅│   │   │   └── 第4段: "25522135" ❌ 超过255│   │   ├── 第3段: "52" ✅│   │   │   └── 第4段: "5522135" ❌ 超过255│   │   └── 第3段: "525" ❌ 超过255│   └── ... (还有很多尝试)│第N次尝试（第1段取"255"）:├── 第1段: "255" ✅│   ├── 第2段: "2" ✅│   │   └── ... (继续尝试)│   ├── 第2段: "25" ✅│   │   └── ... (继续尝试)│   └── 第2段: "255" ✅│       ├── 第3段: "2" ✅│       │   └── 第4段: "2135" ❌ 超过255│       ├── 第3段: "22" ✅│       │   └── 第4段: "135" ✅✅✅ 找到！→ "255.255.22.135"│       └── 第3段: "221" ✅│           └── 第4段: "35" ✅✅✅ 找到！→ "255.255.221.35"

6.2递归调用栈示意图

backtrack(0, [])    │    ├─→ 取 "2" → backtrack(1, ["2"])    │       │    │       └─→ 取 "5" → backtrack(2, ["2","5"])    │               │    │               └─→ ... (继续深入)    │    ├─→ 取 "25" → backtrack(2, ["25"])    │       │    │       └─→ ... (继续深入)    │    └─→ 取 "255" → backtrack(3, ["255"])            │            └─→ ... (最终找到答案)

七、时间与空间复杂度分析

7.1 时间复杂度

理论上界：O(3⁴) = O(81)，可视为 O(1) 常数时间

为什么？

分析：                                 - 字符串最多12个字符              - 需要分成4段                          - 每段最多3种选择（1位、2位、3位）    最坏情况：每个位置都尝试3种长度         递归深度：4层（4段）       每层分支：最多3个         时间复杂度 ≈ 3 × 3 × 3 × 3 = 3⁴ = 81    

详细分析：

实际运行时，由于剪枝优化，很多分支会被提前放弃，所以实际运行次数远小于81次。

7.2 空间复杂度

空间复杂度：O(12) ≈ O(1) 常数空间

空间使用分析：1. 递归调用栈深度：最多4层（4段）   └── 空间：O(4) = O(1)2. 每层的 parts 列表：最多存4个元素   └── 空间：O(4) = O(1)3. 结果列表 result：最多存有限个IP地址   └── 对于12位字符串，最多有多少种合法IP？       理论上限：3⁴ = 81个       实际远小于这个数

7.4 复杂度对比表

八、总结

  一、回溯三要素：选择、约束、目标                               - 选择：每段取1位、2位或3位                               - 约束：无前导零、0-255范围                                   - 目标：分出4段，用完所有字符                            二、剪枝两条件：                                            - 剩余字符太少 → 不够分                                    - 剩余字符太多 → 分不完                               三、边界两检查：                                                 - 前导零检查：length>1 且以'0'开头                            - 数值检查：int(segment) > 255