93. 复原IP地址
Medium
思路
不同类型的题目还是要反复做一做，太久没有做回溯的题，这道题做的时候稍微就有点费劲了
- 对于一个ip地址的字符串来说，我们要把这个字符串分为4段。每段的数字是
0-255，那么我们可以截取[1-3]，长度的字符，再将不合要求的去除。借用李威威大佬解题中的图来说明
- 使用回溯算法。常规操作定义一个
helper方法s: 需要处理的字符串begin: 此次节点开始选择数字的在s中的起始位置path: 记录到当前节点的路径（回溯常规变量）cnt: 当前已经分了多少个区域了，ip地址是四个区域，这个也是我们的终止递归需要判断的条件res: 用于记录符合条件的路径
以上，尝试写一下代码，AC！
代码
python3
class Solution:
def helper(self, s, start, cnt, path, res):
if cnt > 4:
return
elif cnt == 4:
if start == len(s):
res.append('.'.join(path))
return
for i in range(1,4):
if start+i > len(s):
break
sub = s[start:start+i]
if len(sub) > 1 and sub.startswith('0'):
return
if int(sub) > 255:
return
path.append(sub)
self.helper(s,start+i, cnt+1, path, res)
path.pop()
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
self.helper(s, 0, 0, [], res)
return res