数字字符串转化成 IP 地址

1、参考资料

https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e

2、题目要求

题目描述

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525511135",

返回["255.255.11.135", "255.255.111.35"](顺序没有关系)

示例

输入

"25525511135"

输出

["255.255.11.135","255.255.111.35"]

3、代码思路

深度优先搜索

这种题其实和迷宫问题类似，我当前搜寻的路径是否能组成有效的 IP 地址，必须要递归到最深层(递归到 IP 地址中最后一段地址)，才能知道是否为有效的 IP 地址
每个地址段由 1~3 个数字组成，所以我们需要用个 for 循环来搜索这三种情况：for (int i = startIndex; i < startIndex + 3 && i < str.length(); i++) {，即该地址段可能由 1 个数字组成，也可能是 2 个，也有可能是 3 个
那么我们回过头来再想想，递归函数的形参到底需要什么参数呢？源字符串 String str 肯定需要，每一段 IP 地址都需要在源字符串中有个起始索引 int startIndex，还需要有个当前搜索路径记录每段的 IP 地址 List<String> paths，最后的结果(所有合法的 IP 地址)我们使用类变量 ArrayList<String> result 存储
我们定义 void restoreIpAddresses(String str, int startIndex, List<String> paths) { 函数，其目的是将数字字符串转换为 IP 地址，二话不说，写递归先写回溯条件：当凑出有效的 IP 地址回溯，即 paths.size() == 4 回溯；或者是当前的 IP 地址不符合要求时开始回溯(不在 0~255 范围之间，这点在写代码的过程中才能想得到)
每个 IP 地址段的长度可能为 1~3，所以我们需要搜索这三种可能性，使用 for 循环：if (paths.size() == 4) {，在 for 循环里面有一些细节要处理：如果当前 IP 地址段是最后一段，则直接截取字符串的剩余部分(str.substring(startIndex, str.length()))，做合法性判断之后，直接跳出 for 循环(因为最后一段地址只有一种可能)；否则按照正常处理逻辑，即使用循环变量 i+1 作为 IP 地址段的右边界(str.substring(startIndex, i + 1))
由于 List<String> paths 对象属于引用传递，所以整个递归过程中 paths 对象只有一份，我们在进入递归之前，将当前合法的 IP 地址段添加至 paths 中：paths.add(subNum.toString());；然后进入递归：restoreIpAddresses(str, i + 1, paths);；最后恢复现场：paths.remove(paths.size() - 1);。这都是写递归的套路啊，详细可以参考我的博客：组合总和和全排列
还有就是之前说的：当前的 IP 地址不符合要求时开始回溯(不在 0~255 范围之间)，因为这种情况下不能搜索出合法的 IP 地址，所以直接回溯至上一层，然后继续搜索

4、代码实现

代码

class Solution {ArrayList<String> result = new ArrayList<>();public ArrayList<String> restoreIpAddresses(String str) {restoreIpAddresses(str, 0, new ArrayList<>());return result;}private void restoreIpAddresses(String str, int startIndex, List<String> paths) {// 当凑出有效的 IP 地址回溯，即 paths.size() == 4 回溯if (paths.size() == 4) {result.add(paths.get(0) + "." + paths.get(1) + "." + paths.get(2) + "." + paths.get(3));return;}// 每个 IP 地址段的长度可能为 1~3，所以我们需要搜索这三种可能性for (int i = startIndex; i < startIndex + 3 && i < str.length(); i++) {// 截取当前 IP 字符串String subStr = (paths.size() == 3) ? str.substring(startIndex, str.length()) : str.substring(startIndex, i + 1);// 解析当前 IP 地址值Integer subNum = Integer.parseInt(subStr);// 如果 IP 地址合法if (subNum >= 0 && subNum <= 255) {// 将当前合法的 IP 地址段添加至 paths 中paths.add(subNum.toString());// 递归搜索restoreIpAddresses(str, i + 1, paths);// 恢复现场paths.remove(paths.size() - 1);} else {// 当前的 IP 地址不符合要求时开始回溯(不在 0~255 范围之间)return;}if (paths.size() == 3) {break;}}}
}