题目：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 Falset = 0 if not num == 0 else 1while num:num //= 10t += 1if n > t:return Falsereturn True其中对比数位的操作同时验证①和②两个规则
（2）逐位验证数字 and 验证数字大小：
def is_validIP(self, s):n = len(s)if s[0] == '0' and len(s) > 1:return Falsenum = 0for i in range(n):if not s[i].isdigit():return Falsenum = num * 10 + int(s[i])if num > 255:return Falsereturn 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 Falset = 0 if not num == 0 else 1while num:num //= 10t += 1if n > t:return Falsereturn Truedef backtracking(self, s, start_idx, path, ans):if len(path) == 4:if start_idx == len(s):ans.append('.'.join(path))returnfor 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:breakdef 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 Falsenum = 0if n > 1 and s[0] == '0':return Falsefor i in range(n):if not s[i].isdigit():return Falsenum = num * 10 + int(s[i])return 0 <= num <= 255def backtracking(self, s, start_idx, pointnum, path, ans):if pointnum == 3:if self.is_valid(s[start_idx:]):ans.append(path + s[start_idx:])returnfor 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:breakdef 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))returnfor 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):breakch = s[start_idx: i + 1]if int(ch) > 255:breakpath.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
