有效 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","255.255.111.35"]
示例 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"]
提示:
- 1 <= s.length <= 20
- s 仅由数字组成
思路:
- 初始化:设置一个常量 SEG_COUNT 表示 IP 地址段的数量,初始化一个数组 segments 来存储每一段的数值,以及一个数组 res 来存储最终的有效 IP 地址。
- 深度优先搜索(DFS):定义一个递归函数 dfs,它接收当前字符串 s、当前段的编号 segId 和当前段的起始索引 segStart 作为参数。
- 基本情况:如果已经找到 4 段 IP 地址且遍历完字符串,则将当前的 segments 组合加入到答案数组 res 中。
- 提前回溯:如果还没有找到 4 段 IP 地址但已经遍历完字符串,则提前结束当前路径的搜索。
- 处理前导 0:如果当前字符是'0',则该段只能是'0',直接进入下一段。
- 枚举每一位的可能性:对于非前导 0 的情况,尝试每一位的可能性,直到该段的数值超过 255 或遍历完字符串为止。
- 递归搜索:对于每一段,如果数值有效(在 0 到 255 之间),则将其添加到 segments 中,并递归搜索下一段。
- 主函数调用:在主函数中调用 dfs 函数开始搜索。
算法复杂度 时间复杂度:O(4^N),其中 N 是字符串 s 的长度。对于每一段,我们最多有 4 种选择(1 到 3 位数),因此复杂度是指数级的。 空间复杂度:O(1),除了输入字符串和输出数组外,我们只使用了常数级别的额外空间。
var restoreIpAddresses = function (s) {
const SEG_COUNT = 4;
const segments = new Array(SEG_COUNT);
const res = [];
const dfs = (s, segId, segStart) => {
// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
if (segId === SEG_COUNT) {
if (segStart === s.length) {
res.push(segments.join('.'));
}
return;
}
// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯
if (segStart === s.length) {
return;
}
// 由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0
if (s.charAt(segStart) === '0') {
segments[segId] = 0;
dfs(s, segId + 1, segStart + 1);
return;
}
// 一般情况,枚举每一种可能性并递归
let addr = 0;
for (let segEnd = segStart; segEnd < s.length; ++segEnd) {
addr = addr * 10 + (s.charAt(segEnd) - '0');
if (addr > 0 && addr <= 0xff) {
segments[segId] = addr;
dfs(s, segId + 1, segEnd + 1);
} else {
break;
}
}
};
dfs(s, 0, 0);
return res;
};