知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 73 - 复原IP地址 ## 题目(LeetCode 93) 给定只包含数字的字符串,返回所有可能的有效 IP 地址。 ## 解法:回溯 ```java class Solution { public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), res); return res; } private void backtrack(String s, int start, List<String> parts, List<String> res) { if (parts.size() == 4) { if (start == s.length()) res.add(String.join(".", parts)); return; } for (int len = 1; len <= 3 && start + len <= s.length(); len++) { String part = s.substring(start, start + len); if (part.length() > 1 && part.startsWith("0")) break; if (Integer.parseInt(part) > 255) break; parts.add(part); backtrack(s, start + len, parts, res); parts.remove(parts.size() - 1); } } } ``` ## 复杂度 - 时间 O(1)(IP 地址长度有限),空间 O(1) ## 一句话总结 回溯切割,每段 1-3 位,不能有前导零且不超过 255。 ## 说明 复原 IP 地址是回溯的经典题,每段 1-3 位且不超过 255,总共只有 4 段,搜索空间极小(最多 3^4 = 81 种分法)。当前回溯解法已是最优,时间复杂度实际上是 O(1)(输入长度有上限)。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入