【LeetCode】93. 复原IP地址

【LeetCode】93. 复原IP地址

一、题目描述

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。

示例 1：

输入：s = "25525511135"输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"输出：["0.0.0.0"]

示例 3：

输入：s = "1111"输出：["1.1.1.1"]

示例 4：

输入：s = "010010"输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "101023"输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

0 <= s.length <= 3000s 仅由数字组成

二、解题思路 & 代码

2.1 暴力

class Solution: def restoreIpAddresses(self, s: str) -> List[str]: n = len(s) res = [] # 判读是否满足ip的条件 def helper(tmp): if not tmp or (tmp[0] == "0" and len(tmp) > 1) or int(tmp) > 255: return False return True # 三个循环,把数字分成四份 for i in range(3): for j in range(i + 1, i + 4): for k in range(j + 1, j + 4): if i < n and j < n and k < n: tmp1 = s[:i + 1] tmp2 = s[i + 1:j + 1] tmp3 = s[j + 1:k + 1] tmp4 = s[k + 1:] # print(tmp1, tmp2, tmp3, tmp4) if all(map(helper, [tmp1, tmp2, tmp3, tmp4])): res.append(tmp1 + "." + tmp2 + "." + tmp3 + "." + tmp4) return

2.2 递归

class Solution: def restoreIpAddresses(self, s: str) -> List[str]: SEG_COUNT = 4 ans = list() segments = [0] * SEG_COUNT def dfs(segId: int, segStart: int): # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案 if segId == SEG_COUNT: if segStart == len(s): ipAddr = ".".join(str(seg) for seg in segments) ans.append(ipAddr) return # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯 if segStart == len(s): return # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0 if s[segStart] == "0": segments[segId] = 0 dfs(segId + 1, segStart + 1) # 一般情况，枚举每一种可能性并递归 addr = 0 for segEnd in range(segStart, len(s)): addr = addr * 10 + (ord(s[segEnd]) - ord("0")) if 0 < addr <= 0xFF: segments[segId] = addr dfs(segId + 1, segEnd + 1) else: break dfs(0, 0) return

参考：

​​LeetCode官方题解​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。