算法面试-LeetCode-0093复原IP地址
2020-12-13 02:04
标签：result 现在 完成后 backtrack 否则 add 更新 删除 列表 算法面试-LeetCode-0093复原IP地址 标签：result 现在 完成后 backtrack 否则 add 更新 删除 列表 原文地址：https://www.cnblogs.com/max520liuhu/p/11025786.html 回溯(DFS)
这是一个回溯函数backtrack(prev_pos = -1, dots = 3) 的算法，该函数使用上一个放置的点 prev_pos 和待放置点的数量 dots 两个参数 :
遍历三个有效位置curr_pos 以放置点
检查从上一个点到现在点中间的部分是否有效 :
是 :
放置该点。
检查全部 3个点是否放好:
是 :
将结果添加到输出列表中。
否 :
继续放下一个点 backtrack(curr_pos, dots - 1)。
回溯，移除最后一个点
class RestoreIpAddress(object):
def __init__(self, s):
"""
output为最终符合要求的列表
segments为存储符合要求的截取部分的列表
"""
self._s = s
self.length = len(s)
self.output, self.segments = [], []
def is_valid(self, segment):
"""
1. 截取的部分的整数必须小于或者等于255
2. 截取部分除非是0否则不可以以0开头
3. 返回bool
"""
return int(segment)