LeetCode 93. 复原IP地址 | Python
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 93. 复原IP地址 | Python,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2545字,纯文字阅读大概需要4分钟。
内容图文
![LeetCode 93. 复原IP地址 | Python](/upload/InfoBanner/zyjiaocheng/627/a7923e3189d240559b05e18fb7078bcb.jpg)
93. 复原IP地址
题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/restore-ip-addresses
题目
给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
解题思路
思路: 回溯
先看题目,题目要求的是给定一个只包含数字的字符串,复原返回所有可能的 IP 地址格式。至于 IP 地址的有效格式,是由 4 个整数(0~255),整数间用 '.' 分隔组成。
首先,根据题目,借助示例来看下:
s = "25525511135"
假设,给定的字符串如上面示例,那么我们在第一个片段中,我们有三种选择的可能:
- 选 '2';
- 选 '25';
- 选 '255'。
当第一片段选择完毕后,后续的三个片段,也以同样的形式去选择。但是我们在选择的过程中可能会出错,如果出错的话,此时我们就需要撤销这项选择,转而去尝试另外一个选择。
同样的,这里我们的选择是有依据的,并非随意选择。由题目,我们也可以发现,每个片段可选择的数字区间在 [0, 255] 之间,这里也表示长度不能超过 3。
这里还有个需要注意的,题目中并没有明确指出。每个片段中选择的数字是不能有前导 0 的,0 可以作为一个选择,但是不能出现 '0...' 这样的形式,这个也是在测试用例没过的时候发现的。╮(╯▽╰)╭
前面说了选择以及限制,那我们如何才能确认,当选择完毕之后,选择组成的片段就是有效的?
- 首先,要在前面所述的限制条件下进行选择;
- 再来,题目要求复原,也就是,我们选择完 4 个片段之后,必须是要用完所有字符的。
- 如果选择完毕,但是没有用完字符,表示此项选择不符合,返回,回溯;如果先用完字符,但是没有找齐 4 个片段,同样回溯。
- 因为复原的结果可能不止一种,当找到有效的组合,存入返回列表中,继续搜索直至所有可能的选择都尝试一次。
具体的代码实现如下(含注释)。
代码实现
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
# 这里初始化长度为 4 的列表,分别存储对应 4 个片段
sub_res = [0] * 4
def dfs(seg_id, seg_first):
# 先看找到 4 个片段的情况
# 这里可能出现字符完全使用,以及未使用完全的情况
if seg_id == 4:
# 使用完全则添加到列表后返回
if seg_first == len(s):
res.append('.'.join(str(seg)for seg in sub_res))
# 未完全使用则直接返回
return
# 若未找到 4 个片段,则继续查找
# 这里要注意未找到 4 个片段却使用完字符的情况
if seg_first == len(s):
return
# 不能存在前导 0,如果有 0,那么当前片段只能为单独 0
if s[seg_first] == "0":
sub_res[seg_id] = 0
dfs(seg_id+1, seg_first+1)
addr = 0
# 每个片段选择的情况
for seg_last in range(seg_first, len(s)):
# 这里用整型来表示,后面再转换为字符串类型,避免过于频繁的切片
addr = addr * 10 + (ord(s[seg_last]) - ord('0'))
# 大于 0,但小于等于 255 的情况
if 0 < addr <= 255:
sub_res[seg_id] = addr
dfs(seg_id+1, seg_last+1)
# 其他情况直接跳出循环
else:
break
dfs(0, 0)
return res
实现结果
欢迎关注
公众号 【书所集录】
内容总结
以上是互联网集市为您收集整理的LeetCode 93. 复原IP地址 | Python全部内容,希望文章能够帮你解决LeetCode 93. 复原IP地址 | Python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。