从给定的数字字符串生成所有可能的IP地址

1. 概述

本文将探讨在Java中从给定数字字符串生成所有可能IP地址的不同方法。这是一个常见的面试题，我们将深入分析问题陈述，并介绍多种解决方案，包括暴力迭代、回溯和动态规划。

2. 理解问题

给定一个仅包含数字的字符串S，目标是通过在S中插入点号来生成所有有效的IP地址。不能删除或重排任何数字，结果顺序不限。

例如，对于字符串"101024"，输出应为：

["1.0.10.24","1.0.102.4","10.1.0.24","10.10.2.4","101.0.2.4"]

有效的IPv4地址由四个用点分隔的八位组组成，每个八位组是0到255之间的数字。有效IPv4地址示例：

0.0.0.0
192.168.0.8
234.223.43.42
255.255.255.0

3. 迭代法

这种方法使用三层嵌套循环遍历可能的分割位置：外层循环处理第一部分，中间循环处理第二部分，内层循环处理第三部分，剩余部分作为第四段。

获得分段组合后，使用isValid()方法验证每段是否符合IP地址规范。该方法检查数值范围（0-255）并排除前导零：

public List<String> restoreIPAddresses(String s) {
    List<String> result = new ArrayList<>();

    if (s.length() < 4 || s.length() > 12) {
        return result;
    }

    for (int i = 1; i < 4; i++) {
        for (int j = i + 1; j < Math.min(i + 4, s.length()); j++) {
            for (int k = j + 1; k < Math.min(j + 4, s.length()); k++) {
                String part1 = s.substring(0, i);
                String part2 = s.substring(i, j);
                String part3 = s.substring(j, k);
                String part4 = s.substring(k);

                if (isValid(part1) && isValid(part2) && isValid(part3) && isValid(part4)) {
                    result.add(part1 + "." + part2 + "." + part3 + "." + part4);
                }
            }
        }
    }
    return result;
}

private boolean isValid(String part) {
    if (part.length() > 1 && part.startsWith("0")) {        return false;    }
    int num = Integer.parseInt(part);
    return num >= 0 && num <= 255;
}

restoreIPAddresses()方法生成并返回所有有效IP地址。它首先检查字符串长度是否在4-12字符范围内，否则返回空列表（因为无法形成有效IP）。

使用嵌套循环遍历所有可能的点号位置，导致时间复杂度为O(n²)（不是O(n³)，因为外层循环迭代次数固定）。每次迭代创建临时子串，空间复杂度为O(n)。

4. 回溯法

回溯法通过将字符串分成四部分生成所有可能的IP地址。每步使用相同的isValid()方法验证字符串是否非空且无前导零。若有效则继续处理下一段，当四段完整且用尽所有字符时，将结果加入列表：

public List<String> restoreIPAddresses(String s) {
    List<String> result = new ArrayList<>();
    backtrack(result, s, new ArrayList<>(), 0);
    return result;
}

private void backtrack(List<String> result, String s, List<String> current, int index) {
    if (current.size() == 4) {
        if (index == s.length()) {
            result.add(String.join(".", current));
        }
        return;
    }

    for (int len = 1; len <= 3; len++) {
        if (index + len > s.length()) {            break;
        }
        String part = s.substring(index, index + len);
        if (isValid(part)) {
            current.add(part);
            backtrack(result, s, current, index + len);
            current.remove(current.size() - 1);
        }
    }
}

backtrack函数将字符串分成4个整数段，每段最多3位数字，产生3⁴种分割方式。验证每段有效性耗时O(1)（仅需检查长度和范围）。由于3⁴是常数（与输入长度无关），时间复杂度简化为O(1)。

递归深度限制为4（IP地址固定4段），**空间复杂度简化为O(1)**（配置数量和所需空间均为常数）。

5. 动态规划法

动态规划使用递推公式求解问题，类似于分治策略。我们使用dp数组存储所有有效IP前缀：初始化二维列表dp，其中dp[i][j]存储到第i个字符、j个段的所有可能IP地址段。检查所有可能段长（1-3），用isValid()验证。若有效，将其附加到前一状态的前缀：

public List<String> restoreIPAddresses(String s) {
    int n = s.length();
    if (n < 4 || n > 12) {        return new ArrayList<>();
    }
    List<String>[][] dp = new ArrayList[n + 1][5];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 4; j++) {
            dp[i][j] = new ArrayList<>();
        }
    }

    dp[0][0].add("");

    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= 4; k++) {
            for (int j = 1; j <= 3 && i - j >= 0; j++) {
                String segment = s.substring(i - j, i);
                if (isValid(segment)) {
                    for (String prefix : dp[i - j][k - 1]) {
                        dp[i][k].add(prefix.isEmpty() ? segment : prefix + "." + segment);
                    }
                }
            }
        }
    }

    return dp[n][4];
}

初始化dp数组耗时O(n4)→O(n)。填充dp表的嵌套循环耗时O(n43)→O(n)。空间复杂度O(n4)→O(n)。

6. 结论

本文讨论了从给定数字字符串生成所有可能IP地址组合的方法，并分析了多种解决方案：

✅ 迭代法：实现简单，但时间复杂度较高（O(n²)） ✅ 动态规划法：时间复杂度优化至O(n) ✅ 回溯法：效率最高，时间复杂度达O(1)

回溯法在所有方案中表现最佳，提供了最优的O(1)时间复杂度，是处理此类问题的理想选择。

Persistence

REST

Security