93. 复原 IP 地址
【注意】
1.切割问题就可以使用回溯搜索法把所有可能性搜出来。
2.startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
3.本题我们还需要一个变量pointNum，记录添加逗点的数量。
4.分割的段数作为终止条件。pointNum表示逗点数量（决定了树的深度），pointNum为3说明字符串分成了4段了。
5.循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。如果合法就在字符串后面加上符号.表示已经分割。
6.左闭右闭。
【代码】
1 class Solution(object): 2 def __init__(self): 3 self.result = [] 4 def restoreIpAddresses(self, s): 5 """ 6 :type s: str 7 :rtype: List[str] 8 """ 9 ''' 10 本质切割问题使用回溯搜索法，本题只能切割三次，所以纵向递归总共四层 11 因为不能重复分割，所以需要start_index来记录下一层递归分割的起始位置 12 添加变量point_num来记录逗号的数量[0,3] 13 ''' 14 if len(s) > 12: 15 return [] 16 #递归回溯 17 self.backtracking(s,0,0) 18 return self.result 19 20 def backtracking(self,s,start_index,point_num): 21 if point_num == 3: 22 if self.is_valid(s, start_index, len(s)-1):#判断最后一个子串段是否满足 23 self.result.append(s[:]) 24 return 25 26 for i in range(start_index, len(s)): 27 # [start_index, i]就是被截取的子串 28 if self.is_valid(s, start_index, i): 29 s = s[:i+1]+'.'+s[i+1:] 30 # 在填入.后，下一子串起始后移2位 31 self.backtracking(s,i+2,point_num+1) 32 # 回溯 33 s = s[:i+1]+s[i+2:] 34 else: 35 # 若当前被截取的子串大于255或者大于三位数，直接结束本层循环 36 break 37 38 def is_valid(self,s,start,end): 39 if start > end: 40 return False 41 # 若数字是0开头，不合法 42 if s[start] == '0' and start != end: 43 return False 44 if not 0 <= int(s[start:end+1]) <= 255: 45 return False 46 return True