知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 10 - 复原 IP 地址 ## 题目(LeetCode 93) 给定一个只包含数字的字符串 s,返回所有可能的有效 IP 地址。有效 IP 地址由四个整数组成(0~255),用 `.` 分隔,不能有前导零。 ``` 输入:"25525511135" 输出:["255.255.11.135", "255.255.111.35"] ``` ## 大白话理解 在数字串里插入 3 个点,把它分成 4 段,每段是 0~255 的数字,不能有前导零。 这就是"分割回文串"的变体: - 分割回文串:切成若干段,每段是回文 - 复原 IP:切成恰好 4 段,每段是合法的 IP 数字 ``` "25525511135" 切法 1:2.5.5.25511135 → 25511135 > 255 ✗ 切法 2:25.5.25.511135 → 511135 > 255 ✗ ... 切法 N:255.255.11.135 → 每段都合法 ✓ 切法 M:255.255.111.35 → 每段都合法 ✓ ``` ## 代码 ```java class Solution { private List<String> result = new ArrayList<>(); public List<String> restoreIpAddresses(String s) { // IP 地址最少 4 位,最多 12 位 if (s.length() < 4 || s.length() > 12) return result; backtrack(s, 0, new ArrayList<>()); return result; } private void backtrack(String s, int startIndex, List<String> segments) { // 已经切了 4 段 if (segments.size() == 4) { // 必须刚好用完所有字符 if (startIndex == s.length()) { result.add(String.join(".", segments)); } return; } // 每段最多 3 个字符 for (int len = 1; len <= 3; len++) { if (startIndex + len > s.length()) break; // 越界 String segment = s.substring(startIndex, startIndex + len); // 验证合法性 if (!isValid(segment)) continue; segments.add(segment); // 做选择 backtrack(s, startIndex + len, segments); // 递归 segments.remove(segments.size() - 1); // 撤销 } } private boolean isValid(String segment) { // 前导零:长度 > 1 且以 0 开头 if (segment.length() > 1 && segment.charAt(0) == '0') return false; // 数值范围:0~255 int num = Integer.parseInt(segment); return num >= 0 && num <= 255; } } ``` ### 和分割回文串的对比 ``` 分割回文串: 段数不限 终止条件:startIndex == s.length() 合法性:是回文 复原 IP: 恰好 4 段 终止条件:segments.size() == 4 && startIndex == s.length() 合法性:0~255 且无前导零 每段长度:1~3(额外约束) ``` ### 剪枝优化 ```java // 可以加一个提前终止的剪枝 int remainLen = s.length() - startIndex; int remainSegments = 4 - segments.size(); // 剩余字符太少或太多 if (remainLen < remainSegments || remainLen > remainSegments * 3) return; ``` ## 画图模拟 ``` s = "25525511135" segments=[], start=0 切 "2": segments=["2"], start=1 切 "5": segments=["2","5"], start=2 切 "5": segments=["2","5","5"], start=3 切 "25511135": 长度>3 ✗ 切 "255": segments=["2","5","5","255"], start=6 ≠ 11 ✗ ... ... ... 切 "25": segments=["25"], start=2 切 "5": segments=["25","5"], start=3 ... 切 "255": segments=["255"], start=3 切 "2": segments=["255","2"], start=4 ... 切 "25": segments=["255","25"], start=5 ... 切 "255": segments=["255","255"], start=6 切 "1": segments=["255","255","1"], start=7 切 "1135": 长度>3 ✗ 切 "113": 113≤255 ✓ → start=10 ≠ 11 ✗ 切 "11": → segments=["255","255","1","11"] ✗ (还剩 "35") ... 切 "11": segments=["255","255","11"], start=8 切 "135": 135≤255 ✓ → start=11 == 11 ✓ → 收集 "255.255.11.135" ✓ 切 "111": segments=["255","255","111"], start=9 切 "35": 35≤255 ✓ → start=11 == 11 ✓ → 收集 "255.255.111.35" ✓ 结果:["255.255.11.135", "255.255.111.35"] ``` ## 复杂度 - 时间:O(3^4 × n),每段最多 3 种长度,共 4 段 - 空间:O(n) ## 一句话总结 切割问题,恰好切 4 段,每段 1~3 个字符,值在 0~255 且无前导零。标准回溯模板。 --- 上一篇:[09 - 括号生成](./09-generate-parentheses.md) | 返回:[目录](./README.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入