JavaScript 递归（复原 IP 地址）
2020-05-06 本文已影响0人
阿畅_
题目：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
- 从示例中看出，好像分割字符串就可以了，但不是这样的，例如：如果是 1111 也可以是 1.1.1.1
- 题目中看出，可以分割成 4 个部分，每部分的范围是 0 ~ 255
思路
- "25525511135" 根据 IP 的规则，可以分割成 4 部分，每部分 1 ~ 3 个数，每部分范围是 0 ~ 255 ，所有不知道处理多少次，所有要使用递归的方式
从第一个数开始循环每次 截取 1 ~ 3 个数字，判断是否在 IP 规则范围内，然后递归操作，最后递归结束，符合条件的保存到数组中 - 使用递归处理数据
function restoreIpAddresses(str) {
// 当前这里可以加一个判断 字符串的条件，字符串长度必须大于等于 4
// 保存所有符合条件的 IP 地址
let s = []
let search = (cur, sub) => {
// 递归的边界条件，数组长度等于 4 且组合起来与之前的字符串相等
if (cur.length === 4 && cur.join('') === str) {
s.push(cur.join('.'))
} else {
// 处理正常过程
// 每次最多循环三次
let len = Math.min(3, sub.length)
for (let i = 0; i < len; i++) {
// 截取字符串 1 ~ 3
let tmp = sub.substr(0, i + 1)
// 如果当前的数小于 256 说明在 255 范围内，接着递归调用(把不是范围内的排出掉)
// 例如 255255255， 截取第一次 2，第二次递归截取时 for循环第三次是 522 不在范围内
if(tmp < 256) {
search(cur.concat([tmp]), sub.substr(i + 1))
}
}
}
}
search([], str)
return s
}
console.log(restoreIpAddresses('123123'))
["1.2.3.123", "1.2.31.23", "1.23.1.23", "1.23.12.3", "1.231.2.3", "12.3.1.23", "12.3.12.3", "12.31.2.3", "123.1.2.3"]
