leetcode 93. 复原 IP 地址 python

leetcode 93. 复原 IP 地址 python

题目描述：

 

 题解：（参考leetcode评论区回答）

1.和之前的回溯算法解决组合排列问题相同，res记录最终结果，path记录当前搜索路径，当s中所有字符都被使用并且path找到四个有效部分时，将path加入res。

2.不同于之前的组合排列问题，每次选择一个值加入path，此题中每次向path添加的内容可以是当前可用字符串s的前1-3个字符。

 3.从s中剔除已经被使用的部分，s只保存可以使用的部分。

4.每次判断选择加入的部分是否满足不包含先导0和在0-255的范围的条件，不满足则不需要展开搜索。

5.可以提前判断s剩余可用的字符是否大于path缺失部分可以使用的最多字符数进行剪枝。

class Solution(object):
    def restoreIpAddresses(self, s):
        res = []
        self.dfs(res,[],s)
        return res

    def dfs(self,res,path,s):
        if len(s)==0 and len(path)==4:
            res.append(".".join(path))
            return
        if len(s)>3*(4-len(path)):
            return
        for i in range(min(3,len(s))):
            curr = s[:i+1]
            if (curr[0]=='0' and len(curr)>=2) or int(curr)>255:
                continue
            self.dfs(res,path+[curr],s[i+1:])