代码随想录算法训练营第二十八天|93. 复原 IP 地址

【参考链接】

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