共计 1534 个字符,预计需要花费 4 分钟才能阅读完成。
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
实现后果
欢送关注
公众号【书所集录】
正文完