个人主页代码不加冰欢迎来访作者简介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.1681.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仅由数字组成题目解析拿到这个题目我们很轻松的就能看出来这是个切割的问题和我们昨天做的切割回文串是一种题目这里只是换了一个情景根据ip地址的格式来切割让我们先来看看ip地址的格式是啥IP 地址组成规则一个有效的 IPv4 地址由4 个整数组成每个整数范围0-255用点.分隔。例如192.168.1.1规则细节总共 4 段每段长度 1-3 位每段数值范围0 ~ 255不能有前导 0除非该段本身就是0什么是前导 0前导 0指的是数字前面多写的无意义的 0。✅ 合法0、1、255❌ 非法前导 001、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; }常见不合理情况总结情况示例原因长度 31234最多3位数前导 001,000规范禁止数值 255256,300超出范围空串无内容非数字本题不会出现12a字符非法其实只要意识到这是切割问题切割问题就可以使用回溯搜索法把所有可能性搜出来和刚做过的切割回文串就十分类似了。切割问题可以抽象为树型结构如图回溯三部曲递归参数在前面我们就提到切割问题类似组合问题。startIndex一定是需要的因为不能重复分割记录下一层递归分割的起始位置。本题我们还需要一个变量pointNum记录添加逗点的数量。所以代码如下vectorstring 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要从i2开始因为需要在字符串中加入了分隔符.同时记录分割符的数量pointNum 要 1。回溯的时候就将刚刚加入的分隔符.删掉就可以了pointNum也要-1。实际代码理解条件1remainingChars remainingParts剩余字符太少不够分每段至少需要 1 个字符如果剩余字符数 剩余段数说明有人要分到 0 个字符不可能条件2remainingChars remainingParts * 3剩余字符太多分不完每段最多 3 个字符如果剩余字符数 剩余段数 × 3说明就算每段都取满 3 个也装不完核心理解为什么循环len截止是3java 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, startlen) 这段作为当前段的候选 }以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段演示textstart0 / | \ len1 len2 len3 取2 取25 取255 | | | start1 start2 start3 取剩余 取剩余 取剩余 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);举例如果当前段是256isValid()会返回false255就会跳过这个长度不会继续递归。if (start len s.length()) break这行代码是在检查从当前start位置开始能否取出len个字符如果取不出来会超出字符串长度就提前结束循环不再尝试更长的len。为什么是break而不是continue因为len是从小到大递增的1, 2, 3如果len1就越界 → 说明start已经在字符串末尾了如果len2就越界 → 说明只剩 1 个字符不可能取 2 个或 3 个一旦某个长度越界更长的长度也一定会越界所以用break直接退出循环没必要继续尝试更大的len。图解示例场景1正常情况texts 255255, start 4 字符串: 2 5 5 2 5 5 索引: 0 1 2 3 4 5 ↑ start4 len1: start15 ≤ 6? 是 ✅ → 取 s[4] 5 len2: start26 ≤ 6? 是 ✅ → 取 s[4..5] 55 len3: start37 ≤ 6? 否 ❌ → break退出循环场景2快结束时texts 255255, start 5 字符串: 2 5 5 2 5 5 索引: 0 1 2 3 4 5 ↑ start5 len1: start16 ≤ 6? 是 ✅ → 取 s[5] 5 len2: start27 ≤ 6? 否 ❌ → break不会再尝试 len3场景3已在末尾texts 255255, start 6已经处理完所有字符 len1: start17 ≤ 6? 否 ❌ → break循环直接结束题目答案import java.util.ArrayList; import java.util.List; public class Solution { public ListString restoreIpAddresses(String s) { ListString 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, ListString parts, ListString 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; } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
【LeetCode刷题日记】93.复原IP地址
发布时间：2026/6/8 0:12:17
个人主页代码不加冰欢迎来访作者简介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.1681.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仅由数字组成题目解析拿到这个题目我们很轻松的就能看出来这是个切割的问题和我们昨天做的切割回文串是一种题目这里只是换了一个情景根据ip地址的格式来切割让我们先来看看ip地址的格式是啥IP 地址组成规则一个有效的 IPv4 地址由4 个整数组成每个整数范围0-255用点.分隔。例如192.168.1.1规则细节总共 4 段每段长度 1-3 位每段数值范围0 ~ 255不能有前导 0除非该段本身就是0什么是前导 0前导 0指的是数字前面多写的无意义的 0。✅ 合法0、1、255❌ 非法前导 001、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; }常见不合理情况总结情况示例原因长度 31234最多3位数前导 001,000规范禁止数值 255256,300超出范围空串无内容非数字本题不会出现12a字符非法其实只要意识到这是切割问题切割问题就可以使用回溯搜索法把所有可能性搜出来和刚做过的切割回文串就十分类似了。切割问题可以抽象为树型结构如图回溯三部曲递归参数在前面我们就提到切割问题类似组合问题。startIndex一定是需要的因为不能重复分割记录下一层递归分割的起始位置。本题我们还需要一个变量pointNum记录添加逗点的数量。所以代码如下vectorstring 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要从i2开始因为需要在字符串中加入了分隔符.同时记录分割符的数量pointNum 要 1。回溯的时候就将刚刚加入的分隔符.删掉就可以了pointNum也要-1。实际代码理解条件1remainingChars remainingParts剩余字符太少不够分每段至少需要 1 个字符如果剩余字符数 剩余段数说明有人要分到 0 个字符不可能条件2remainingChars remainingParts * 3剩余字符太多分不完每段最多 3 个字符如果剩余字符数 剩余段数 × 3说明就算每段都取满 3 个也装不完核心理解为什么循环len截止是3java 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, startlen) 这段作为当前段的候选 }以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段演示textstart0 / | \ len1 len2 len3 取2 取25 取255 | | | start1 start2 start3 取剩余 取剩余 取剩余 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);举例如果当前段是256isValid()会返回false255就会跳过这个长度不会继续递归。if (start len s.length()) break这行代码是在检查从当前start位置开始能否取出len个字符如果取不出来会超出字符串长度就提前结束循环不再尝试更长的len。为什么是break而不是continue因为len是从小到大递增的1, 2, 3如果len1就越界 → 说明start已经在字符串末尾了如果len2就越界 → 说明只剩 1 个字符不可能取 2 个或 3 个一旦某个长度越界更长的长度也一定会越界所以用break直接退出循环没必要继续尝试更大的len。图解示例场景1正常情况texts 255255, start 4 字符串: 2 5 5 2 5 5 索引: 0 1 2 3 4 5 ↑ start4 len1: start15 ≤ 6? 是 ✅ → 取 s[4] 5 len2: start26 ≤ 6? 是 ✅ → 取 s[4..5] 55 len3: start37 ≤ 6? 否 ❌ → break退出循环场景2快结束时texts 255255, start 5 字符串: 2 5 5 2 5 5 索引: 0 1 2 3 4 5 ↑ start5 len1: start16 ≤ 6? 是 ✅ → 取 s[5] 5 len2: start27 ≤ 6? 否 ❌ → break不会再尝试 len3场景3已在末尾texts 255255, start 6已经处理完所有字符 len1: start17 ≤ 6? 否 ❌ → break循环直接结束题目答案import java.util.ArrayList; import java.util.List; public class Solution { public ListString restoreIpAddresses(String s) { ListString 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, ListString parts, ListString 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; } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
