Open
Description
给定一个只包含数字的字符串，复原它并返回所有可能的 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
}