【LeetCode刷题日记】93.复原IP地址

🔥个人主页：代码不加冰（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：LeetCode刷题日记 ， 苍穹外卖日记，SSM框架深入，JavaWeb，
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好，我是代码不加冰，今天又到了我们的每日刷题环节，今天我们要刷的是对应力扣的93题，是相关回溯算法这方面的。

摘要：

本文介绍了如何通过回溯算法解决LeetCode 93题「复原IP地址」问题。文章详细解析了IP地址的组成规则（4段0-255的数字，无前导0），并通过示例展示了有效与无效IP的区别。作者使用Java实现了回溯算法，通过递归尝试1-3个字符的分割，结合剪枝优化（剩余字符检查）和合法性验证（长度、前导0、数值范围），最终生成所有可能的有效IP地址。代码包含核心的backtrack方法和isValid校验逻辑，适用于长度4-12的输入字符串。该解法将问题抽象为树形结构，与分割回文串思路类似，展现了回溯算法的典型应用场景。

题目背景：93.复原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 地址。

给定一个只包含数字的字符串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 <= 20
• s仅由数字组成

题目解析：

拿到这个题目，我们很轻松的就能看出来这是个切割的问题，和我们昨天做的切割回文串是一种题目，这里只是换了一个情景，根据ip地址的格式来切割，让我们先来看看ip地址的格式是啥：

IP 地址组成规则

一个有效的 IPv4 地址由4 个整数组成，每个整数范围0-255，用点.分隔。例如：192.168.1.1

规则细节：

1. 总共 4 段，每段长度 1-3 位

2. 每段数值范围：0 ~ 255

3. 不能有前导 0（除非该段本身就是0）

---

什么是前导 0

前导 0指的是数字前面多写的无意义的 0。

• ✅ 合法："0"、"1"、"255"

• ❌ 非法（前导 0）："01"、"00"、"001"、"010"

原因：IP 地址每一段是数字表示，不是字符串。01会被解析成 1，但规范不允许这样写。

---

不合理的判断（无效段）

判断一个字符串segment是否合法：

java private boolean isValid(String segment) { if (segment == null || segment.length() == 0) return false; // 长度超过3位 → 非法 if (segment.length() > 3) return false; // 前导0：长度>1 且 第一个字符是'0' → 非法 if (segment.length() > 1 && segment.charAt(0) == '0') return false; // 数值范围检查 int num = Integer.parseInt(segment); return num >= 0 && num <= 255; }

常见不合理情况总结：

情况	示例	原因
长度 > 3	"1234"	最多3位数
前导 0	"01","000"	规范禁止
数值 > 255	"256","300"	超出范围
空串	""	无内容
非数字（本题不会出现）	"12a"	字符非法

其实只要意识到这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的切割回文串就十分类似了。

切割问题可以抽象为树型结构，如图：

回溯三部曲

• 递归参数

在前面我们就提到切割问题类似组合问题。

startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。

本题我们还需要一个变量pointNum，记录添加逗点的数量。

所以代码如下：

vector<string> result;// 记录结果 // startIndex: 搜索的起始位置，pointNum:添加逗点的数量 void backtracking(string& s, int startIndex, int pointNum) {

• 递归终止条件

终止条件和我们之前做的切割回文串情况就不同了，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。

pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。

然后验证一下第四段是否合法，如果合法就加入到结果集里

代码如下：

if (pointNum == 3) { // 逗点数量为3时，分隔结束 // 判断第四段子字符串是否合法，如果合法就放进result中 if (isValid(s, startIndex, s.size() - 1)) { result.push_back(s); } return; }

• 单层搜索的逻辑

在131.分割回文串 中已经讲过在循环遍历中如何截取子串。

在for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。

如果合法就在字符串后面加上符号.表示已经分割。

如果不合法就结束本层循环，如图中剪掉的分支：

然后就是递归和回溯的过程：

递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。

回溯的时候，就将刚刚加入的分隔符.删掉就可以了，pointNum也要-1。

实际代码理解：

条件1：remainingChars < remainingParts

剩余字符太少，不够分

• 每段至少需要 1 个字符

• 如果剩余字符数 < 剩余段数，说明有人要分到 0 个字符（不可能）

条件2：remainingChars > remainingParts * 3

剩余字符太多，分不完

• 每段最多 3 个字符

• 如果剩余字符数 > 剩余段数 × 3，说明就算每段都取满 3 个，也装不完

核心理解

为什么循环len截止是3

java for (int len = 1; len <= 3; len++) { // len = 1: 尝试截取1个字符作为当前段 // len = 2: 尝试截取2个字符 // len = 3: 尝试截取3个字符 if (start + len > s.length()) break; // 防止索引越界：如果从start开始取len个字符会超出字符串长度，就停止 String segment = s.substring(start, start + len); // 从字符串中截取 [start, start+len) 这段作为当前段的候选 }

以s = "25525511135"，当前start = 0（刚开始处理）为例：

text

字符串: 2 5 5 2 5 5 1 1 1 3 5 索引: 0 1 2 3 4 5 6 7 8 9 10 当前 start = 0 len = 1: 截取 segment = "2" (索引0) len = 2: 截取 segment = "25" (索引0-1) len = 3: 截取 segment = "255"(索引0-2) 每种长度都会递归下去继续处理剩余字符串

为什么要循环 1-3

因为 IP 地址每一段的合法长度只能是：

长度	示例	说明
1 位	"0"~"9"	单个数字
2 位	"10"~"99"	两个数字
3 位	"100"~"255"	三个数字（但不能超过 255）

不能是 0 位（每段至少 1 个数字）
不能超过 3 位（最大 255 只需要 3 位）

---

完整的决策树演示

以s = "255255"（简化版，只用2段演示）：

text

start=0 / | \ len=1 len=2 len=3 取"2" 取"25" 取"255" | | | start=1 start=2 start=3 取剩余 取剩余 取剩余 "55255" "5255" "255" | | | 继续递归... 继续递归... 继续递归...

配合 isValid() 的剪枝

不是所有长度都能成功，需要通过isValid(segment)过滤：

java String segment = s.substring(start, start + len); if (!isValid(segment)) continue; // 不合法就跳过，尝试下一个长度 parts.add(segment); backtrack(s, start + len, parts, result); // 递归处理下一段 parts.remove(parts.size() - 1);

举例：如果当前段是"256"，isValid()会返回false（>255），就会跳过这个长度，不会继续递归。

if (start + len > s.length()) break

这行代码是在检查：从当前start位置开始，能否取出len个字符

如果取不出来（会超出字符串长度），就提前结束循环，不再尝试更长的len。

---

为什么是break而不是continue

因为len是从小到大递增的（1, 2, 3）：

• 如果len=1就越界 → 说明start已经在字符串末尾了

• 如果len=2就越界 → 说明只剩 1 个字符，不可能取 2 个或 3 个

• 一旦某个长度越界，更长的长度也一定会越界

所以用break直接退出循环，没必要继续尝试更大的len。

图解示例

场景1：正常情况

text

s = "255255", start = 4 字符串: 2 5 5 2 5 5 索引: 0 1 2 3 4 5 ↑ start=4 len=1: start+1=5 ≤ 6? 是 ✅ → 取 s[4] = "5" len=2: start+2=6 ≤ 6? 是 ✅ → 取 s[4..5] = "55" len=3: start+3=7 ≤ 6? 否 ❌ → break（退出循环）

场景2：快结束时

text

s = "255255", start = 5 字符串: 2 5 5 2 5 5 索引: 0 1 2 3 4 5 ↑ start=5 len=1: start+1=6 ≤ 6? 是 ✅ → 取 s[5] = "5" len=2: start+2=7 ≤ 6? 否 ❌ → break（不会再尝试 len=3）

场景3：已在末尾

text

s = "255255", start = 6（已经处理完所有字符） len=1: start+1=7 ≤ 6? 否 ❌ → break（循环直接结束）

题目答案：

import java.util.ArrayList; import java.util.List; public class Solution { public List<String> restoreIpAddresses(String s) { List<String> result = new ArrayList<>(); if (s == null || s.length() < 4 || s.length() > 12) { return result; // 长度不可能构成有效IP } backtrack(s, 0, new ArrayList<>(), result); return result; } /** * 回溯生成IP * @param s 原始字符串 * @param start 当前处理到的索引 * @param parts 当前已选中的段（最多4段） * @param result 结果集 */ private void backtrack(String s, int start, List<String> parts, List<String> result) { // 已完成4段且用完了所有字符 → 有效IP if (parts.size() == 4) { if (start == s.length()) { result.add(String.join(".", parts)); } return; } // 剩余段数 int remainingParts = 4 - parts.size(); // 剩余字符数 int remainingChars = s.length() - start; // 剪枝：剩余字符不够每段1位 或 超过每段3位 if (remainingChars < remainingParts || remainingChars > remainingParts * 3) { return; } // 尝试取1到3个字符作为当前段 for (int len = 1; len <= 3; len++) { // 起始索引不能越界 if (start + len > s.length()) break; String segment = s.substring(start, start + len); // 判断当前段是否合法 if (!isValid(segment)) continue; parts.add(segment); backtrack(s, start + len, parts, result); parts.remove(parts.size() - 1); // 回溯 } } // 判断某一段是否合法 private boolean isValid(String segment) { // 长度超过3直接false if (segment.length() > 3) return false; // 前导0判断：长度>1 且 首位是'0' if (segment.length() > 1 && segment.charAt(0) == '0') return false; // 数值范围判断 int num = Integer.parseInt(segment); return num >= 0 && num <= 255; } }

结语：
如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！