0093.复原 IP 地址
难度:🟡 中等
标签:字符串
、回溯
链接: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"]
示例 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 地址(已经找到了几个段)以及下一个段应该从字符串的哪个位置开始。
关键步骤
定义回溯函数:创建一个递归函数,例如
backtrack(startIndex, path)
。startIndex
:表示当前段应该从字符串s
的哪个索引开始。path
:一个数组,存储已经找到的有效 IP 段。
设置终止条件 (Base Case):
如果
path
中已经有 4 个段,并且startIndex
正好到达了字符串s
的末尾,说明我们找到了一个完整的、有效的 IP 地址。将其加入结果集。如果
path
中已经有 4 个段,但startIndex
未到末尾,或者startIndex
已到末尾但path
不足 4 段,都说明当前路径无效,直接返回。
循环与剪枝: 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
种),然后再去验证。而推荐的回溯法是边分割边验证,一旦发现当前分割无效(如256
或01
),会立即“剪枝”,不再继续向下探索,从而避免了大量不必要的计算。
复杂度分析
时间复杂度:O(3⁴ × |s|) 在最坏情况下,我们需要探索所有可能的分割点。由于 IP 地址只有 4 段,递归深度是常数 4。每个节点有最多 3 个分支(长度为1/2/3),所以搜索空间是有限的,但具体计算与字符串内容相关,较为复杂。
空间复杂度:O(|s|) 空间主要消耗在递归栈(深度为常数 4)和存储路径的
path
数组(长度为 4)以及结果集results
上。
相关题目
总结
本题是回溯算法在字符串分割问题中的一个经典应用。解题的关键在于定义清晰的递归函数、设定正确的终止条件,并有效地进行“剪枝”以减少不必要的搜索。推荐解法中的“边分割边验证”模式是此类问题的通用高效模板。