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"]

分析

本题我们先来观察数据范围，可以发现，就算是每段都为三位的 IP 地址（255），最多也

只有长度为 12 的字符串生成，对吧？

所以，这么小的数据范围，我们不必大费周章考虑别的算法，直接采用搜索算法即可，对

于本题，深度优先搜索是非常不错的选择。

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

算法。

首先我们来确定一下边界条件，用 cnt 来记录 IP 地址段（用.号分割开）的总数，并用

anss[]来记录每个段，等 cnt == 4 时，代表 IP 地址已经切割完成，如果刚好也遍历完了

整个字符串，且没有非法的情况，就可以将 anss[]加入最后的答案。

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

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

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

从当前位置开始枚举，并且用 num 来记录值，当值大于 255 的时候停止枚举，然后将

num 加入 anss[]，并增加一次段的数目 cnt++，再然后进入下一次搜索。

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

class Solution {

List<String> ans = new ArrayList<>(); // 存储最终的结果

int[] anss = new int[4]; // 存储每次递归得到的 IP 段

public List<String> restoreIpAddresses(String s) {

dfs(s, 0, 0); // 从 s 的第 0 位置开始搜索，当前已经得到 0 段 IP

return ans;

}

public void dfs(String s, int cnt, int pos) {

// 如果已经得到 4 段 IP 地址

if (cnt == 4) {

// 并且已经处理完整个字符串

if (pos == s.length()) {

StringBuilder temp = new StringBuilder();

for (int i = 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 为 0

dfs(s, cnt + 1, pos + 1); // 继续递归

} else {

int num = 0; // 用于暂存当前段的 IP 地址

// 尝试每一种可能的组合

for (int i = 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：

1. cnt = 0, pos = 0

– 第一个数字为’2’，不为’0’，所以可以尝试分成 1-3 位数的部分。

– 取 1 位数: 2

– 取 2 位数: 25

– 取 3 位数: 255 (合法，因为它<=255)

– 对于上述的每一个数值，我们都将继续递归地寻找下一部分。

2. 当我们取第一部分为 255 时（其他的取值也类似），继续深入搜索：

– cnt = 1, pos = 3

• 下一个数字为’2’，同样，我们可以尝试 1-3 位数。

• 取 1 位数: 2

• 取 2 位数: 25

• 取 3 位数: 255

3. 如果我们继续取 255 作为第二部分，那么进一步深入：

– cnt = 2, pos = 6

• 下一个数字为’1’

• 取 1 位数: 1

• 取 2 位数: 11

• 取 3 位数: 111

4. 如果我们继续以 111 为第三部分，那么再次深入：

– cnt = 3, pos = 9

• 取 1 位数: 3

• 取 2 位数: 35

• 因为 pos 已经达到字符串末尾，我们不能再取 3 位数。

5. 于是，我们得到一个合法的 IPv4 地址：255.255.111.35。

同理，我们可以通过所有可能的分割方式，使用 DFS 来查找所有合法的 IPv4 地址。最

终，对于输入 25525511135，题解将生成以下两个合法的 IPv4 地址：

• 255.255.11.135

• 255.255.111.35

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

保每一步都符合 IPv4 的规则。

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

093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80-20231027163643.png

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

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class RestoreIPAddresses {

List<String> ans = new ArrayList<>();

int[] anss = new int[4];

public List<String> restoreIpAddresses(String s) {

dfs(s, 0, 0);

return ans;

}

public void dfs(String s, int cnt, int pos) {

if (cnt == 4) {

if (pos == s.length()) {

StringBuilder temp = new StringBuilder();

for (int i = 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 {

int num = 0;

for (int i = 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;

}

}

}

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("请输入给定的 IP 字符串: ");

String s = scanner.next();

RestoreIPAddresses solution = new RestoreIPAddresses();

List<String> result = solution.restoreIpAddresses(s);

System.out.println("可能的 IP 地址有:");

for (String ip : result) {

System.out.println(ip);

}

}

}

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

093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80-20231027165141.png

总结

搜索类的题目通常并非难题，重要的如何将我们内心中模拟的过程完美的复现出来，而多

练习，是我们提高这类解题技巧的最好方式。

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