0093.复原 IP 地址

难度:🟡 中等

标签字符串回溯

链接93. 复原 IP 地址

题目描述

有效 IP 地址 正好由四个整数(每个整数位于 0255 之间组成,且不能含有前导 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"]

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

解题思路

核心思想

本题的本质是一个字符串分割问题。我们需要将给定的数字字符串 s 分割成 4 个部分,并验证每个部分是否满足有效 IP 地址段的要求(0-255,无前导零)。由于涉及到所有可能的分割方式,这自然地导向了 回溯法

思路选择

回溯法(深度优先搜索 DFS) 是解决此问题的标准思路。我们把问题看作是在字符串中选择 3 个位置插入 .

  • 我们可以定义一个递归函数,它负责在字符串的剩余部分中继续寻找合法的 IP 段。

  • 函数需要记录当前正在构建的 IP 地址(已经找到了几个段)以及下一个段应该从字符串的哪个位置开始。

关键步骤

  1. 定义回溯函数:创建一个递归函数,例如 backtrack(startIndex, path)

    • startIndex:表示当前段应该从字符串 s 的哪个索引开始。

    • path:一个数组,存储已经找到的有效 IP 段。

  2. 设置终止条件 (Base Case)

    • 如果 path 中已经有 4 个段,并且 startIndex 正好到达了字符串 s 的末尾,说明我们找到了一个完整的、有效的 IP 地址。将其加入结果集。

    • 如果 path 中已经有 4 个段,但 startIndex 未到末尾,或者 startIndex 已到末尾但 path 不足 4 段,都说明当前路径无效,直接返回。

  3. 循环与剪枝: a. 从 startIndex 开始,循环尝试截取长度为 1、2、3 的子串作为当前 IP 段。 b. 验证与剪枝:对截取的子串进行合法性检查: i. 前导零:如果子串长度大于 1 且以 '0' 开头,则该子串无效,后续更长的子串也必然无效,可以直接剪枝(结束当前层的循环)。 ii. 数值范围:将子串转为数字,如果大于 255,则该子串无效,后续更长的子串也必然无效,同样可以剪枝。 c. 做出选择与递归:如果子串合法,就将其加入 path,并从该子串的下一位开始,递归调用回溯函数。 d. 撤销选择:当深层递归返回后,将之前加入的 IP 段从 path 中弹出,以便尝试其他可能性。

代码实现

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    const results = [];
    const path = []; // 存放当前已分割的 IP 段

    const backtrack = (startIndex) => {
        // 如果已找到 4 段,并且字符串也用完了,说明找到一个有效解
        if (path.length === 4 && startIndex === s.length) {
            results.push(path.join('.'));
            return;
        }

        // 如果段数已满或字符串已用完,但条件不符,则剪枝
        if (path.length === 4 || startIndex === s.length) {
            return;
        }

        // 尝试分割长度为 1, 2, 3 的段
        for (let len = 1; len <= 3; len++) {
            // 越界检查
            if (startIndex + len > s.length) break;

            const segment = s.substring(startIndex, startIndex + len);

            // 剪枝:处理前导零 (如 "01")
            if (segment.length > 1 && segment.startsWith('0')) break;
            // 剪枝:处理数值范围
            if (parseInt(segment) > 255) break;

            // 做出选择
            path.push(segment);
            // 递归
            backtrack(startIndex + len);
            // 撤销选择
            path.pop();
        }
    };

    backtrack(0);
    return results;
};

原始代码分析 (用户提供)

您提供的解法思路比较独特,它不是直接对字符串进行分割,而是先通过回溯生成所有可能的 IP段长度组合(例如 [3, 3, 2, 3]),然后检查这些长度组合是否能构成一个有效的 IP 地址。

// 检查单个 IP 段是否有效
var isValid = function (str) {
    let num = parseInt(str);
    // 检查范围,并通过字符串比较来处理前导零的情况
    if (num < 0 || num > 255 || num.toString() !== str) return false;
    return true;
}

// 通过回溯生成所有可能的长度组合
var backTracking = function (choices, path, results, target) {
    // 当找到一个 4 段的长度组合时
    if (path.length === 4) {
        // 检查总长度是否等于目标字符串长度
        const total = path.reduce((a, b) => a + b, 0);
        if (total === target.length) {
            let point = 0, result = [];
            // 按长度组合来分割和验证字符串
            for (let i = 0; i < path.length; i++) {
                const subStr = target.substr(point, path[i]);
                if (isValid(subStr)) result.push(subStr);
                else return; // 如果有一段无效,则整个组合无效
                point += path[i];
            }
            results.push(result.join('.'));
        }
        return;
    }
    // 递归生成长度组合
    for (let i = 0; i < choices.length; i++) {
        path.push(choices[i]);
        backTracking(choices, path, results, target);
        path.pop();
    }
}
/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
    let choices = [1, 2, 3];
    let results = [];
    backTracking(choices, [], results, s);
    return results;
};
  • 优点:想法新颖,将问题分解为“长度划分”和“有效性验证”两步。

  • 待改进:这种方法的效率较低。它先生成所有可能的长度组合(3^4=81 种),然后再去验证。而推荐的回溯法是边分割边验证,一旦发现当前分割无效(如 25601),会立即“剪枝”,不再继续向下探索,从而避免了大量不必要的计算。

复杂度分析

  • 时间复杂度O(3⁴ × |s|) 在最坏情况下,我们需要探索所有可能的分割点。由于 IP 地址只有 4 段,递归深度是常数 4。每个节点有最多 3 个分支(长度为1/2/3),所以搜索空间是有限的,但具体计算与字符串内容相关,较为复杂。

  • 空间复杂度O(|s|) 空间主要消耗在递归栈(深度为常数 4)和存储路径的 path 数组(长度为 4)以及结果集 results 上。

相关题目

总结

本题是回溯算法在字符串分割问题中的一个经典应用。解题的关键在于定义清晰的递归函数、设定正确的终止条件,并有效地进行“剪枝”以减少不必要的搜索。推荐解法中的“边分割边验证”模式是此类问题的通用高效模板。

Copyright © Jun 2025 all right reserved,powered by Gitbook该文件修订时间: 2025-07-03 17:35:08

results matching ""

    No results matching ""

    results matching ""

      No results matching ""