[网络协议]leetcode系列-93.复原 IP 地址

leetcode系列–第93题.复原 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 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

事例：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
输入：s = "0000"
输出：["0.0.0.0"]
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
  let length = s.length
  let result = []
  let path = []
  fnHelp(0)
  return result

  function fnHelp(startIndex) {
    // 递归的退出条件
    if (path.length > 4) {
      return
    }
    if (path.length === 4 && startIndex === length) {
      result.push(path.join('.'))
      return
    }

    for (let i = startIndex; i < length; i++) {
      const temp = s.substr(startIndex, i - startIndex + 1)
      if (temp.length > 3 || +temp > 255) break;
      if (temp.length > 1 && temp[0] === "0") break;
      path.push(temp)
      fnHelp(i + 1)
      path.pop()
    }
  }
};