复原IP地址-93
sl1673495 opened this issue · 1 comments
sl1673495 commented
给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
利用一个辅助的 DFS函数,每次可以传入当前起始的位置,和当前已使用的.
的数量,然后通过范围在 1 ~ 3
来继续分割出不同的下一位ip地址。
当.
的使用数到达3的时候,就直接判断剩余的字符是否满足ip条件,满足的放入数组即可。
这题本身并不难,但是边界情况比较多。比如说如果分割出来的一块地址开头是0的话,那么必须只有一位,也就是 0
,而不能是 01
或者001
这种。
/**
* @param {string} s
* @return {string[]}
*/
let restoreIpAddresses = function (s) {
let res = []
let findPos = (start, prev, used) => {
if (used === 3) {
let rest = s.substr(start)
// 点全部用光后 剩余字符依然是一个合格的ip chunk
// 就视为一个答案 放入数组
if (isValidChunk(rest)) {
res.push(prev.concat(rest).join("."))
}
return
}
for (let i = 1; i <= 3; i++) {
let end = start + i
let cur = s.substring(start, end)
if (isValidChunk(cur)) {
findPos(end, prev.concat(cur), used + 1)
}
}
}
findPos(0, [], 0)
return res
}
function isValidChunk(str) {
let strLen = str.length
if (strLen === 0) {
return false
}
// 开头是0的话 只能整个字符串只有一位0才行
if (str[0] === "0") {
return strLen === 1
}
let num = Number(str)
return num <= 255
}
jinfang12345 commented
function test(str, remain=4) {
const result = [];
if (remain === 1) {
if (Number(str) <= 255 && Number(str) > 0) {
return [str];
} else {
return undefined;
}
}
for (let index = 1; index < 4; index++) {
const a = str.substring(0, index);
if (Number(a) > 0 && Number(a) <= 255) {
const b = test(str.substring(index), remain - 1);
if (b && b.length) {
b.forEach(item => {
result.push([a].concat(item).join('.'));
});
}
}
}
return result;
}