LeetCode 0093. Restore IP Addresses复原IP地址【Python】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 0093. Restore IP Addresses复原IP地址【Python】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1807字，纯文字阅读大概需要3分钟。
内容图文
LeetCode 0093. Restore IP Addresses复原IP地址【Medium】【Python】【回溯】【DFS】【暴力】
Problem
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
问题
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
思路
解法一
回溯 DFS
回溯算法的关键就是合理剪枝，这个也是难点。
详细可以看代码注释。
下面剪枝图片来源于 liweiwei1419 的 回溯算法（画图分析剪枝条件）
Python3代码
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
# solution one: backtracking
ans = []
self.dfs(s, [], ans)
return ans
def dfs(self, s, path, ans):
if len(s) > (4 - len(path)) * 3: # pruning: len(s) > 12
return
if not s and len(path) == 4: # remove first '.' and IP address should be 4 parts
ans.append('.'.join(path))
return
for i in range(min(3, len(s))):
cur = s[:i + 1]
if(cur[0] == '0' and len(cur) >= 2) or int(cur) > 255: # invalid IP address
continue
self.dfs(s[i + 1:], path + [s[:i + 1]], ans)
解法二
暴力
暴力出奇迹
四次 for 遍历，再分别取四部分作为地址，分别判断是否合法。
最后拼接一下，加入 ans 中。
Python3代码
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
# solution two: brute force search
ans = []
for a in range(1, 4):
for b in range(1, 4):
for c in range(1, 4):
for d in range(1, 4):
if a + b + c + d == len(s):
ss = [s[:a], s[a:a+b], s[a+b:a+b+c], s[a+b+c:]]
flag = 0
for k in range(4):
if int(ss[k]) > 255:
flag = 1
break
if len(ss[k]) >= 2 and ss[k][0] == '0': # for example: 0xx.xxx.xxx.xxx
flag = 1
break
if flag == 0:
ans.append(ss[0] + '.' + ss[1] + '.' + ss[2] + '.' + ss[3])
return ans
代码地址
参考
【LeetCode】93. Restore IP Addresses 解题报告（Python & C++）
LeetCode-93-Restore IP Addresses 暴力
原文：https://www.cnblogs.com/wonz/p/12416065.html
内容总结
以上是互联网集市为您收集整理的LeetCode 0093. Restore IP Addresses复原IP地址【Python】全部内容，希望文章能够帮你解决LeetCode 0093. Restore IP Addresses复原IP地址【Python】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。