LeetCode 题解工作台
复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0 ），整数之间用 '.' 分隔。 例如： "0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245" 、 "192.168.1.312" 和 "192.…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们定义一个函数 ，表示从字符串 的第 位开始，搜索能够组成的 IP 地址列表。 函数 的执行步骤如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
有效 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 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20s仅由数字组成
解题思路
方法一：DFS
我们定义一个函数 ，表示从字符串 的第 位开始，搜索能够组成的 IP 地址列表。
函数 的执行步骤如下：
如果 大于等于字符串 的长度，说明已经完成了四段 IP 地址的拼接，判断是否满足四段 IP 地址的要求，如果满足则将当前 加入答案。
如果 小于字符串 的长度，此时还需要拼接 地址的一段，此时需要确定这一段 地址的值。如果该值大于 ，或者当前位置 为 且 之后的若干位的数值大于 ，则说明不满足要求，直接返回。否则，将其加入 地址列表，并继续搜索下一段 地址。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def check(i: int, j: int) -> int:
if s[i] == "0" and i != j:
return False
return 0 <= int(s[i : j + 1]) <= 255
def dfs(i: int):
if i >= n and len(t) == 4:
ans.append(".".join(t))
return
if i >= n or len(t) >= 4:
return
for j in range(i, min(i + 3, n)):
if check(i, j):
t.append(s[i : j + 1])
dfs(j + 1)
t.pop()
n = len(s)
ans = []
t = []
dfs(0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(M ^ N \cdot N), where M is the maximum segment length (3) and N is the string length, due to recursive exploration. Space complexity is O(M \cdot N) for the recursion stack and temporary segment storage. |
| 空间 | O(M \cdot N) |
面试官常问的追问
外企场景- question_mark
Expect candidates to handle leading zeros correctly and prune invalid paths.
- question_mark
Look for efficient recursive or iterative backtracking rather than brute-force splitting.
- question_mark
Watch if candidate avoids unnecessary string copying and joins segments carefully.
常见陷阱
外企场景- error
Not pruning segments larger than 255 leads to TLE.
- error
Allowing leading zeros in multi-digit segments generates invalid addresses.
- error
Incorrectly handling string bounds when placing dots can cause out-of-range errors.
进阶变体
外企场景- arrow_right_alt
Return only the first k valid IP addresses instead of all.
- arrow_right_alt
Count the total number of valid IP addresses without listing them.
- arrow_right_alt
Generate IP addresses for a string that may contain non-digit separators, ignoring them in validation.