递归 复原 IP 地址

题目：给定一个只包含数字的字符串，复原它并返回所有可能的 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. 从第一个数开始循环每次 截取 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"]