题目
题目来源:力扣(LeetCode)
给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 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 地址。
示例 1:
输入:s = “25525511135”
输出:[“255.255.11.135”,”255.255.111.35”]
示例 2:
输入:s = “0000”
输出:[“0.0.0.0”]
示例 3:
输入:s = “1111”
输出:[“1.1.1.1”]
示例 4:
输入:s = “010010”
输出:[“0.10.0.10”,”0.100.1.0”]
示例 5:
输入:s = “101023”
输出:[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]
思路分析
回溯
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function (s) {
// SEG_COUNT=4 表示 IP 地址的段数
const SEG_COUNT = 4;
// segments 存储已经搜索过的 IP 地址
const segments = new Array(SEG_COUNT);
const ans = [];
/**
*
* @param s | 数字字符串
* @param segId | IP地址片段
* @param segStart 搜索的起始位置
* @returns
*/
const dfs = (s, segId, segStart) => {
// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
if (segId === SEG_COUNT) {
if (segStart === s.length) {
ans.push(segments.join('.'));
}
return;
}
// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯
if (segStart === s.length) {
return;
}
// 由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0
if (s.charAt(segStart) === '0') {
segments[segId] = 0;
// 进入下一个IP片段的寻找
dfs(s, segId + 1, segStart + 1);
}
// 一般情况,枚举每一种可能性并递归
let addr = 0;
for (let segEnd = segStart; segEnd < s.length; ++segEnd) {
addr = addr * 10 + (s.charAt(segEnd) - '0'); // (s.charAt(segEnd) - '0') 转换成 int 类型
// 以0x开始的数据表示16进制,0xFF换成十进制为255
if (addr > 0 && addr <= 0xFF) { // 当前IP段数字在0 ~ 255 之间,符合要求
// 设置IP片段的值
segments[segId] = addr;
// 进入下一个IP片段的寻找
dfs(s, segId + 1, segEnd + 1);
} else {
// 不合法,结束本层循环
break;
}
}
}
dfs(s, 0, 0);
return ans;
};