4664 字
约 15 分钟
10
093.复原 IP 地址
2026-09-19
数据结构与算法
无标签

093.复原 IP 地址

作者：沉默王二
发布时间：2023-10-27T16:53:37.294+0800

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected] " 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

难度

中等

示例

示例 1：

输入：s="25525511135"

示例 2：

输入：s="0000"

示例 3：

输入：s="101023"

分析

本题我们先来观察数据范围，可以发现，就算是每段都为三位的 IP 地址（255），最多也只有长度为 12 的字符串生成，对吧？

所以，这么小的数据范围，我们不必大费周章考虑别的算法，直接采用搜索算法即可，对于本题，深度优先搜索是非常不错的选择。

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。

首先我们来确定一下边界条件，用cnt来记录 IP 地址段（用.号分割开）的总数，并用anss[]来记录每个段，等cnt == 4时，代表 IP 地址已经切割完成，如果刚好也遍历完了整个字符串，且没有非法的情况，就可以将anss[]加入最后的答案。

其次，还有一个点需要注意，那就是遇到0的情况，我们该如何抉择？

当然是直接加入anss[]，并且向后继续访问输入s。因为0不能作为段的开头。

如果是非零的情况，则需要枚举。

从当前位置开始枚举，并且用num来记录值，当值大于255的时候停止枚举，然后将num加入anss[]，并增加一次段的数目cnt++，再然后进入下一次搜索。

多说无益，不如我们仔细看看代码：

classSolution{

int[]anss=newint[4];//存储每次递归得到的IP段
publicListrestoreIpAddresses(Strings){dfs(s,0,0);//从s的第0位置开始搜索，当前已经得到0段IPreturnans;}
publicvoiddfs(Strings,intcnt,intpos){//如果已经得到4段IP地址if(cnt==4){//并且已经处理完整个字符串if(pos==s.length()){StringBuildertemp=newStringBuilder();for(inti=0;i<4;i++){temp.append(anss[i]);if(i!=3){temp.append(".");}}ans.add(temp.toString());}return;}//如果当前位置已经超过字符串长度if(pos==s.length()){return;}//如果当前位置字符为'0'if(s.charAt(pos)=='0'){anss[cnt]=0;//直接保存该段IP为0dfs(s,cnt+1,pos+1);//继续递归}else{intnum=0;//用于暂存当前段的IP地址//尝试每一种可能的组合for(inti=pos;i<s.length();i++){num=num*10+(s.charAt(i)-'0');//检查当前数字是否有效if(num>0&&num<=255){anss[cnt]=num;//保存当前段IP地址dfs(s,cnt+1,i+1);//继续递归}else{break;//如果当前数字不再合法范围内，直接跳出}}}}}

题解中有一个小的知识点，对于任何从'0'到'9'的数字字符，charAt(i) - '0'都会返回其对应的整数值。

当输入是"25525511135"时我们来模拟一下整个题解过程。

我们开始在s的开头执行dfs：

  • cnt = 0, pos = 0
  • 第一个数字为'2'，不为'0'，所以可以尝试分成1-3位数的部分。
  • 取1位数: 2
  • 取2位数: 25
  • 取3位数: 255 (合法，因为它<=255)
  • 对于上述的每一个数值，我们都将继续递归地寻找下一部分。
  • 当我们取第一部分为255时（其他的取值也类似），继续深入搜索：
  • cnt = 1, pos = 3
  • 下一个数字为'2'，同样，我们可以尝试1-3位数。
  • 取1位数: 2
  • 取2位数: 25
  • 取3位数: 255
  • 如果我们继续取255作为第二部分，那么进一步深入：
  • cnt = 2, pos = 6
  • 下一个数字为'1'
  • 取1位数: 1
  • 取2位数: 11
  • 取3位数: 111
  • 如果我们继续以111为第三部分，那么再次深入：
  • cnt = 3, pos = 9
  • 取1位数: 3
  • 取2位数: 35
  • 因为pos已经达到字符串末尾，我们不能再取3位数。
  • 于是，我们得到一个合法的IPv4地址：255.255.111.35。

同理，我们可以通过所有可能的分割方式，使用DFS来查找所有合法的IPv4地址。最终，对于输入25525511135，题解将生成以下两个合法的IPv4地址：

  • 255.255.11.135
  • 255.255.111.35

整个过程就是一个标准的DFS，从前到后地搜索字符串，每一步都尝试1到3个字符，确保每一步都符合IPv4的规则。

我们来看一下整个题解的效率：

如果感兴趣的话，还可以通过 ACM 输入输出的方式在 Intellij IDEA 中进行调试。

importjava.util.ArrayList;

importjava.util.Scanner;
publicclassRestoreIPAddresses{Listans=newArrayList<>();int[]anss=newint[4];
publicListrestoreIpAddresses(Strings){dfs(s,0,0);returnans;}
publicvoiddfs(Strings,intcnt,intpos){if(cnt==4){if(pos==s.length()){StringBuildertemp=newStringBuilder();for(inti=0;i<4;i++){temp.append(anss[i]);if(i!=3){temp.append(".");}}ans.add(temp.toString());}return;}if(pos==s.length()){return;}if(s.charAt(pos)=='0'){anss[cnt]=0;dfs(s,cnt+1,pos+1);}else{intnum=0;for(inti=pos;i<s.length();i++){num=num*10+(s.charAt(i)-'0');if(num>0&&num<=255){anss[cnt]=num;dfs(s,cnt+1,i+1);}else{break;}}}}
publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);System.out.print("请输入给定的IP字符串:");Strings=scanner.next();RestoreIPAddressessolution=newRestoreIPAddresses();Listresult=solution.restoreIpAddresses(s);System.out.println("可能的IP地址有:");for(Stringip:result){System.out.println(ip);}}}

输入输出的结果如下所示：

总结

搜索类的题目通常并非难题，重要的如何将我们内心中模拟的过程完美的复现出来，而多练习，是我们提高这类解题技巧的最好方式。

力扣链接：https://leetcode.cn/problems/restore-ip-addresses/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected] " 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

难度

中等

示例

示例 1：

输入：s="25525511135"

示例 2：

输入：s="0000"

示例 3：

输入：s="101023"

分析

本题我们先来观察数据范围，可以发现，就算是每段都为三位的 IP 地址（255），最多也只有长度为 12 的字符串生成，对吧？

所以，这么小的数据范围，我们不必大费周章考虑别的算法，直接采用搜索算法即可，对于本题，深度优先搜索是非常不错的选择。

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。

首先我们来确定一下边界条件，用cnt来记录 IP 地址段（用.号分割开）的总数，并用anss[]来记录每个段，等cnt == 4时，代表 IP 地址已经切割完成，如果刚好也遍历完了整个字符串，且没有非法的情况，就可以将anss[]加入最后的答案。

其次，还有一个点需要注意，那就是遇到0的情况，我们该如何抉择？

当然是直接加入anss[]，并且向后继续访问输入s。因为0不能作为段的开头。

如果是非零的情况，则需要枚举。

从当前位置开始枚举，并且用num来记录值，当值大于255的时候停止枚举，然后将num加入anss[]，并增加一次段的数目cnt++，再然后进入下一次搜索。

多说无益，不如我们仔细看看代码：

classSolution{

int[]anss=newint[4];//存储每次递归得到的IP段
publicListrestoreIpAddresses(Strings){dfs(s,0,0);//从s的第0位置开始搜索，当前已经得到0段IPreturnans;}
publicvoiddfs(Strings,intcnt,intpos){//如果已经得到4段IP地址if(cnt==4){//并且已经处理完整个字符串if(pos==s.length()){StringBuildertemp=newStringBuilder();for(inti=0;i<4;i++){temp.append(anss[i]);if(i!=3){temp.append(".");}}ans.add(temp.toString());}return;}//如果当前位置已经超过字符串长度if(pos==s.length()){return;}//如果当前位置字符为'0'if(s.charAt(pos)=='0'){anss[cnt]=0;//直接保存该段IP为0dfs(s,cnt+1,pos+1);//继续递归}else{intnum=0;//用于暂存当前段的IP地址//尝试每一种可能的组合for(inti=pos;i<s.length();i++){num=num*10+(s.charAt(i)-'0');//检查当前数字是否有效if(num>0&&num<=255){anss[cnt]=num;//保存当前段IP地址dfs(s,cnt+1,i+1);//继续递归}else{break;//如果当前数字不再合法范围内，直接跳出}}}}}

题解中有一个小的知识点，对于任何从'0'到'9'的数字字符，charAt(i) - '0'都会返回其对应的整数值。

当输入是"25525511135"时我们来模拟一下整个题解过程。

我们开始在s的开头执行dfs：

  • cnt = 0, pos = 0
  • 第一个数字为'2'，不为'0'，所以可以尝试分成1-3位数的部分。
  • 取1位数: 2
  • 取2位数: 25
  • 取3位数: 255 (合法，因为它<=255)
  • 对于上述的每一个数值，我们都将继续递归地寻找下一部分。
  • 当我们取第一部分为255时（其他的取值也类似），继续深入搜索：
  • cnt = 1, pos = 3
  • 下一个数字为'2'，同样，我们可以尝试1-3位数。
  • 取1位数: 2
  • 取2位数: 25
  • 取3位数: 255
  • 如果我们继续取255作为第二部分，那么进一步深入：
  • cnt = 2, pos = 6
  • 下一个数字为'1'
  • 取1位数: 1
  • 取2位数: 11
  • 取3位数: 111
  • 如果我们继续以111为第三部分，那么再次深入：
  • cnt = 3, pos = 9
  • 取1位数: 3
  • 取2位数: 35
  • 因为pos已经达到字符串末尾，我们不能再取3位数。
  • 于是，我们得到一个合法的IPv4地址：255.255.111.35。

同理，我们可以通过所有可能的分割方式，使用DFS来查找所有合法的IPv4地址。最终，对于输入25525511135，题解将生成以下两个合法的IPv4地址：

  • 255.255.11.135
  • 255.255.111.35

整个过程就是一个标准的DFS，从前到后地搜索字符串，每一步都尝试1到3个字符，确保每一步都符合IPv4的规则。

我们来看一下整个题解的效率：

如果感兴趣的话，还可以通过 ACM 输入输出的方式在 Intellij IDEA 中进行调试。

importjava.util.ArrayList;

importjava.util.Scanner;
publicclassRestoreIPAddresses{Listans=newArrayList<>();int[]anss=newint[4];
publicListrestoreIpAddresses(Strings){dfs(s,0,0);returnans;}
publicvoiddfs(Strings,intcnt,intpos){if(cnt==4){if(pos==s.length()){StringBuildertemp=newStringBuilder();for(inti=0;i<4;i++){temp.append(anss[i]);if(i!=3){temp.append(".");}}ans.add(temp.toString());}return;}if(pos==s.length()){return;}if(s.charAt(pos)=='0'){anss[cnt]=0;dfs(s,cnt+1,pos+1);}else{intnum=0;for(inti=pos;i<s.length();i++){num=num*10+(s.charAt(i)-'0');if(num>0&&num<=255){anss[cnt]=num;dfs(s,cnt+1,i+1);}else{break;}}}}
publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);System.out.print("请输入给定的IP字符串:");Strings=scanner.next();RestoreIPAddressessolution=newRestoreIPAddresses();Listresult=solution.restoreIpAddresses(s);System.out.println("可能的IP地址有:");for(Stringip:result){System.out.println(ip);}}}

输入输出的结果如下所示：

总结

搜索类的题目通常并非难题，重要的如何将我们内心中模拟的过程完美的复现出来，而多练习，是我们提高这类解题技巧的最好方式。

力扣链接：https://leetcode.cn/problems/restore-ip-addresses/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected] " 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

难度

中等

示例

示例 1：

输入：s="25525511135"

示例 2：

输入：s="0000"

示例 3：

输入：s="101023"

分析

本题我们先来观察数据范围，可以发现，就算是每段都为三位的 IP 地址（255），最多也只有长度为 12 的字符串生成，对吧？

所以，这么小的数据范围，我们不必大费周章考虑别的算法，直接采用搜索算法即可，对于本题，深度优先搜索是非常不错的选择。

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。

首先我们来确定一下边界条件，用cnt来记录 IP 地址段（用.号分割开）的总数，并用anss[]来记录每个段，等cnt == 4时，代表 IP 地址已经切割完成，如果刚好也遍历完了整个字符串，且没有非法的情况，就可以将anss[]加入最后的答案。

其次，还有一个点需要注意，那就是遇到0的情况，我们该如何抉择？

当然是直接加入anss[]，并且向后继续访问输入s。因为0不能作为段的开头。

如果是非零的情况，则需要枚举。

从当前位置开始枚举，并且用num来记录值，当值大于255的时候停止枚举，然后将num加入anss[]，并增加一次段的数目cnt++，再然后进入下一次搜索。

多说无益，不如我们仔细看看代码：

classSolution{

int[]anss=newint[4];//存储每次递归得到的IP段
publicListrestoreIpAddresses(Strings){dfs(s,0,0);//从s的第0位置开始搜索，当前已经得到0段IPreturnans;}
publicvoiddfs(Strings,intcnt,intpos){//如果已经得到4段IP地址if(cnt==4){//并且已经处理完整个字符串if(pos==s.length()){StringBuildertemp=newStringBuilder();for(inti=0;i<4;i++){temp.append(anss[i]);if(i!=3){temp.append(".");}}ans.add(temp.toString());}return;}//如果当前位置已经超过字符串长度if(pos==s.length()){return;}//如果当前位置字符为'0'if(s.charAt(pos)=='0'){anss[cnt]=0;//直接保存该段IP为0dfs(s,cnt+1,pos+1);//继续递归}else{intnum=0;//用于暂存当前段的IP地址//尝试每一种可能的组合for(inti=pos;i<s.length();i++){num=num*10+(s.charAt(i)-'0');//检查当前数字是否有效if(num>0&&num<=255){anss[cnt]=num;//保存当前段IP地址dfs(s,cnt+1,i+1);//继续递归}else{break;//如果当前数字不再合法范围内，直接跳出}}}}}

题解中有一个小的知识点，对于任何从'0'到'9'的数字字符，charAt(i) - '0'都会返回其对应的整数值。

当输入是"25525511135"时我们来模拟一下整个题解过程。

我们开始在s的开头执行dfs：

  • cnt = 0, pos = 0
  • 第一个数字为'2'，不为'0'，所以可以尝试分成1-3位数的部分。
  • 取1位数: 2
  • 取2位数: 25
  • 取3位数: 255 (合法，因为它<=255)
  • 对于上述的每一个数值，我们都将继续递归地寻找下一部分。
  • 当我们取第一部分为255时（其他的取值也类似），继续深入搜索：
  • cnt = 1, pos = 3
  • 下一个数字为'2'，同样，我们可以尝试1-3位数。
  • 取1位数: 2
  • 取2位数: 25
  • 取3位数: 255
  • 如果我们继续取255作为第二部分，那么进一步深入：
  • cnt = 2, pos = 6
  • 下一个数字为'1'
  • 取1位数: 1
  • 取2位数: 11
  • 取3位数: 111
  • 如果我们继续以111为第三部分，那么再次深入：
  • cnt = 3, pos = 9
  • 取1位数: 3
  • 取2位数: 35
  • 因为pos已经达到字符串末尾，我们不能再取3位数。
  • 于是，我们得到一个合法的IPv4地址：255.255.111.35。

同理，我们可以通过所有可能的分割方式，使用DFS来查找所有合法的IPv4地址。最终，对于输入25525511135，题解将生成以下两个合法的IPv4地址：

  • 255.255.11.135
  • 255.255.111.35

整个过程就是一个标准的DFS，从前到后地搜索字符串，每一步都尝试1到3个字符，确保每一步都符合IPv4的规则。

我们来看一下整个题解的效率：

如果感兴趣的话，还可以通过 ACM 输入输出的方式在 Intellij IDEA 中进行调试。

importjava.util.ArrayList;

importjava.util.Scanner;
publicclassRestoreIPAddresses{Listans=newArrayList<>();int[]anss=newint[4];
publicListrestoreIpAddresses(Strings){dfs(s,0,0);returnans;}
publicvoiddfs(Strings,intcnt,intpos){if(cnt==4){if(pos==s.length()){StringBuildertemp=newStringBuilder();for(inti=0;i<4;i++){temp.append(anss[i]);if(i!=3){temp.append(".");}}ans.add(temp.toString());}return;}if(pos==s.length()){return;}if(s.charAt(pos)=='0'){anss[cnt]=0;dfs(s,cnt+1,pos+1);}else{intnum=0;for(inti=pos;i<s.length();i++){num=num*10+(s.charAt(i)-'0');if(num>0&&num<=255){anss[cnt]=num;dfs(s,cnt+1,i+1);}else{break;}}}}
publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);System.out.print("请输入给定的IP字符串:");Strings=scanner.next();RestoreIPAddressessolution=newRestoreIPAddresses();Listresult=solution.restoreIpAddresses(s);System.out.println("可能的IP地址有:");for(Stringip:result){System.out.println(ip);}}}

输入输出的结果如下所示：

总结

搜索类的题目通常并非难题，重要的如何将我们内心中模拟的过程完美的复现出来，而多练习，是我们提高这类解题技巧的最好方式。

力扣链接：https://leetcode.cn/problems/restore-ip-addresses/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412
093.复原 IP 地址
https://clxhxhhr.top/posts/2547/
作者
clxstart
发布于
2026-09-19
许可协议
CC BY-NC-SA 4.0
092.反转链表 II
094.二叉树的中序遍历
评论
0 条
还没有评论，先写一条吧。
☰ 文章目录