LeetCode|LeetCode 93. 复原IP地址 | Python LeetCode93.复原IP地址|Python

93. 复原IP地址题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/restore-ip-addresses
题目给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
示例:

输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]

解题思路思路：回溯
先看题目，题目要求的是给定一个只包含数字的字符串，复原返回所有可能的 IP 地址格式。至于 IP 地址的有效格式，是由 4 个整数（0~255），整数间用 '.' 分隔组成。
【LeetCode|LeetCode 93. 复原IP地址 | Python】首先，根据题目，借助示例来看下：

s = "25525511135"

假设，给定的字符串如上面示例，那么我们在第一个片段中，我们有三种选择的可能：

选 '2'；
选 '25'；
选 '255'。

当第一片段选择完毕后，后续的三个片段，也以同样的形式去选择。但是我们在选择的过程中可能会出错，如果出错的话，此时我们就需要撤销这项选择，转而去尝试另外一个选择。
同样的，这里我们的选择是有依据的，并非随意选择。由题目，我们也可以发现，每个片段可选择的数字区间在 [0, 255] 之间，这里也表示长度不能超过 3。

这里还有个需要注意的，题目中并没有明确指出。每个片段中选择的数字是不能有前导 0 的，0 可以作为一个选择，但是不能出现 '0...' 这样的形式，这个也是在测试用例没过的时候发现的。╮(╯▽╰)╭

前面说了选择以及限制，那我们如何才能确认，当选择完毕之后，选择组成的片段就是有效的？

首先，要在前面所述的限制条件下进行选择；
再来，题目要求复原，也就是，我们选择完 4 个片段之后，必须是要用完所有字符的。
如果选择完毕，但是没有用完字符，表示此项选择不符合，返回，回溯；如果先用完字符，但是没有找齐 4 个片段，同样回溯。
因为复原的结果可能不止一种，当找到有效的组合，存入返回列表中，继续搜索直至所有可能的选择都尝试一次。

具体的代码实现如下（含注释）。
代码实现

class Solution: def restoreIpAddresses(self, s: str) -> List[str]: res = [] # 这里初始化长度为 4 的列表，分别存储对应 4 个片段 sub_res = [0] * 4def dfs(seg_id, seg_first): # 先看找到 4 个片段的情况 # 这里可能出现字符完全使用，以及未使用完全的情况 if seg_id == 4: # 使用完全则添加到列表后返回 if seg_first == len(s): res.append('.'.join(str(seg)for seg in sub_res)) # 未完全使用则直接返回 return# 若未找到 4 个片段，则继续查找 # 这里要注意未找到 4 个片段却使用完字符的情况 if seg_first == len(s): return# 不能存在前导 0，如果有 0，那么当前片段只能为单独 0 if s[seg_first] == "0": sub_res[seg_id] = 0 dfs(seg_id+1, seg_first+1)addr = 0 # 每个片段选择的情况 for seg_last in range(seg_first, len(s)): # 这里用整型来表示，后面再转换为字符串类型，避免过于频繁的切片 addr = addr * 10 + (ord(s[seg_last]) - ord('0'))# 大于 0，但小于等于 255 的情况 if 0 < addr <= 255: sub_res[seg_id] = addr dfs(seg_id+1, seg_last+1) # 其他情况直接跳出循环 else: breakdfs(0, 0) return res

实现结果