数字字符串转化成 IP 地址

Love The Way You Lie 2022-12-09 01:55 342阅读 0赞

# 数字字符串转化成 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、代码思路 ##

深度优先搜索

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

说明：我不知道牛客网对于 `0` 的处理是什么方式，反正我就是将字符串 `subStr` 解析成整形数值 `subNum`，然后调用 `subNum.toString()` 去除前导零

![image-20200921110035855][]

[Link 1]: https://blog.csdn.net/oneby1314/article/details/108453151
[Link 2]: https://blog.csdn.net/oneby1314/article/details/108448972
[image-20200921110035855]: /images/20221123/a23a081d07e5467b8abc8c09e7098000.png