93. 复原 IP 地址
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从
s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导
0），整数之间用 '.' 分隔。示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "1111" 输出：["1.1.1.1"]
示例 4：
输入：s = "010010" 输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
0 <= s.length <= 3000
s仅由数字组成
法1 回溯
思路
类似于分割字符串，只不过此题分割出来的是ip的每一段，而不是回文。且只能分割成四段！
怎么判断是不是ip的字段呢？
0≤int(s)≤255 and str(int(s)) == s 前半段是判断是否在[0, 255]之间,后半段是在判断是否是以0开头的字符串。
题解
class Solution: def restoreIpAddresses(self, s: str) -> List[str]: self.res = [] self.dfs(path=[], s=s, start=0) return self.res def dfs(self, path, s, start): if start >= len(s) and len(path)==4: self.res.append(".".join(path)) return if len(path) >= 4: return for i in range(start+1, len(s)+1): # 以i分割， 后面的字符太多了。太多了，可以向后移动i if len(s)-i > (4-len(path)-1)*3 : continue # 以i分割，后面的字符太少了， 太少了没办法只能return if len(s) - i < (4-len(path)-1): return if self.isValid(s[start:i]): path.append(s[start:i]) self.dfs(path, s, i) path.pop() def isValid(self, s): return True if (0 <= int(s) <= 255 and str(int(s)) == s) else False