刷题记录 回溯算法-10：93. 复原 IP 地址
题目：93. 复原 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 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20s仅由数字组成
一、模式识别
1.问题分解
该问题即用回溯法遍历出所有的切割方式，
并逐个判断子串是否合法
因此该题可以分解为切割方式和子串合法性判断两个子问题
2.切割问题
从搜索集看为等效的无重复选取且无重复元素的组合问题，
从结果收集条件看为长度条件和位置（终点）条件共同作用
所以有双重验证条件：
if len(path) == 4:
if start_idx == len(s):
ans.append('.'.join(path))
return但本题无需长度剪枝
因为本题中合法的子串对长度也有要求
长度剪枝的作用会被子串合法性判断剪枝的作用覆盖
3.子串合法性判断
总结下来共三个规则：
①以0为开头的子串不合法
②有非正整数字符不合法
③若子串表示的数字大于255不合法
每切割一个子串都需要验证子串的合法性：
（1）验证数字大小 and 对比数字位数与字符位数：
def is_validIP(self, s):
n = len(s)
num = int(s)
if num < 0 or num > 255:
return False
t = 0 if not num == 0 else 1
while num:
num //= 10
t += 1
if n > t:
return False
return True其中对比数位的操作同时验证①和②两个规则
（2）逐位验证数字 and 验证数字大小：
def is_validIP(self, s):
n = len(s)
if s[0] == '0' and len(s) > 1:
return False
num = 0
for i in range(n):
if not s[i].isdigit():
return False
num = num * 10 + int(s[i])
if num > 255:
return False
return True
由于子串表示数字大小限制，
因此节点搜索集宽度上限为3：
for i in range(start_idx, min(start_idx + 3, len(s))):此外子串合法性判断还有个规律：
包含不合法子串的其他字符串也不合法
因此有：
for i in range(start_idx, len(s)):
ch = s[start_idx: i + 1]
if self.is_validIP(ch):
path.append(ch)
self.backtracking(s, i + 1, path, ans)
path.pop()
else:
break这条规律与子串长度限制的作用相互覆盖，
选择其一即实现剪枝
二.代码实现
本题中存在字符串，
因此有传递数组拼接和传递字符记录点数两种写法
写法一（传递数组拼接）：
class Solution:
def is_validIP(self, s):
n = len(s)
num = int(s)
if num < 0 or num > 255:
return False
t = 0 if not num == 0 else 1
while num:
num //= 10
t += 1
if n > t:
return False
return True
def backtracking(self, s, start_idx, path, ans):
if len(path) == 4:
if start_idx == len(s):
ans.append('.'.join(path))
return
for i in range(start_idx, len(s)):
ch = s[start_idx: i + 1]
if self.is_validIP(ch):
path.append(ch)
self.backtracking(s, i + 1, path, ans)
path.pop()
else:
break
def restoreIpAddresses(self, s: str) -> List[str]:
ans = []
self.backtracking(s, 0, [], ans)
return ans写法二（传递字符串记录点数）：
class Solution:
def is_valid(self, s):
n = len(s)
if n == 0:
return False
num = 0
if n > 1 and s[0] == '0':
return False
for i in range(n):
if not s[i].isdigit():
return False
num = num * 10 + int(s[i])
return 0 <= num <= 255
def backtracking(self, s, start_idx, pointnum, path, ans):
if pointnum == 3:
if self.is_valid(s[start_idx:]):
ans.append(path + s[start_idx:])
return
for i in range(start_idx, len(s)):
ch = s[start_idx: i + 1]
if self.is_valid(ch):
self.backtracking(s, i + 1, pointnum + 1, path + ch + '.', ans)
else:
break
def restoreIpAddresses(self, s: str) -> List[str]:
ans = []
self.backtracking(s, 0, 0, "", ans)
return ans此外，验证函数的逻辑可以写在for循环内部
写法三（for循环内部验证合法性）：
class Solution:
def backtracking(self, s, start_idx, path, ans):
if len(path) == 4:
if start_idx == len(s):
ans.append('.'.join(path))
return
for i in range(start_idx, len(s)):
if s[start_idx] == '0' and i > start_idx:
break
# 长度决定的两种不可能完成路径的情况：
# 剩余路径的最大容量少于剩余的数字：3 * (4 - len(path)) < (len(s) - i)
# 剩余路径的最小需求多于剩余的数字：(4 - len(path)) > (len(s) - i)
if 3 * (4 - len(path)) < (len(s) - i) or (4 - len(path)) > (len(s) - i):
break
ch = s[start_idx: i + 1]
if int(ch) > 255:
break
path.append(ch)
self.backtracking(s, i + 1, path, ans)
path.pop()
def restoreIpAddresses(self, s: str) -> List[str]:
ans = []
self.backtracking(s, 0, [], ans)
return ans