LeetCode0093.RestoreIPAddressesRestoreIPAddress【中】【Python】【回溯】【DFS】【暴力】问题LeetCode给定一个只包含数字的字符串，通过返回所有可能的方式来恢复它有效的IP地址组合。示例：输入：“25525511135”输出：[“255.255.11.135”，“255.255.111.35”]问题给定一个仅包含数字的字符串，将其还原并返回所有可能的IP地址格式。示例：输入："25525511135"输出：["255.255.11.135","255.255.111.35"]思路解决方案1??回溯DFS回溯算法的关键在于合理剪枝，这也是一个难点。有关详细信息，请参阅代码注释。下图剪枝图片来自liweiwei1419的回溯算法（剪枝条件绘制分析）Python3代码类解决方案：defrestoreIpAddresses(self,s:str)->List[str]:#解决方案一：回溯ans=[]self.dfs(s,[],ans)returnansdefdfs(self,s,path,ans):iflen(s)>(4-len(path))*3:#剪枝:len(s)>12returnifnotsandlen(path)==4:#删除第一个'.'IP地址应该是4个部分ans.append('.'.join(path))returnforiinrange(min(3,len(s))):cur=s[:i+1]if(cur[0]=='0'andlen(cur)>=2)orint(cur)>255:#无效IP地址继续self.dfs(s[i+1:],path+[s[:i+1]],ans)解决方案2暴力暴力奇迹遍历四次，然后取四部分作为地址判断是否合法。最后拼接起来，加入到ans中。Python3代码类解决方案：defrestoreIpAddresses(self,s:str)->List[str]:#解决方案二：暴力搜索ans=[]forainrange(1,4):forbinrange(1,4):forcinrange(1,4):fordinrange(1,4):ifa+b+c+d==len(s):ss=[s[:a],s[a:a+b],s[a+b:a+b+c],s[a+b+c:]]flag=0forkinrange(4):ifint(ss[k])>255:flag=1breakiflen(ss[k])>=2andss[k][0]=='0':#例如：0xx.xxx.xxx.xxxflag=1breakifflag==0:ans.append(ss[0]+'.'+ss[1]+'.'+ss[2]+'.'+ss[3])再转ans代码地址GitHub链接参考【LeetCode】93.RestoreIPAddresses解题报告（Python&C++）LeetCode-93-RestoreIPAddresses暴力
