Skip to content

复原IP地址

· 5 min

题目#

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如：

第一个有前导 0，第二个超出了 255，第三个分隔符

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

示例 1

输入：s = “25525511135” 输出：[“255.255.11.135”,“255.255.111.35”]

示例 2

输入：s = “0000” 输出：[“0.0.0.0”]

示例 3

输入：s = “101023” 输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

解题思路

给定一个只含数字的字符串 s，我们要在其中插入三个 '.' 将其拆分为 4 段，每段都必须满足有效 IP 段的要求：

  1. 段数: 切分后必须恰好有 4 段 (形成 A.B.C.D 这种形式)。
  2. 范围: 每段数字必须在 [0, 255] 之间。
  3. 不能有前导零: 如果某段以 '0' 开头，则该段只能是单个 '0' 本身，比如 '01' 或 '00' 都是无效的。

我们可以定义一个函数 backtrack(start, segmentCount, path)：

然后做深度优先遍历：

  1. 如果 segmentCount == 4 且 start 恰好到达字符串末尾 (意味着已经用完所有字符)，说明拼成了一个完整的 4 段 IP，将其加入答案。
  2. 如果 segmentCount == 4 但还没用完字符串，或者已经用完字符串但段数不足 4，则不是有效切分，直接返回。
  3. 否则，从当前 start 位置，试着切取 1~3 个数字作为下一段：
    • 每切取一段，就验证该段是否满足“合法 IP 段”：不能有前导 0（除非段就是单个 ‘0’）且数值 ≤ 255。
    • 若合法，则递归处理下一段，传递 (start + len, segmentCount + 1, path+该段)
    • 回溯时，撤销对 path 的更改，继续尝试其他长度的切分。

通过这种方法，能枚举出所有可能的拆分方式，并过滤掉不合法的分支（这也是剪枝的重要部分：不符合 IP 段要求的直接跳过）。

代码实现

/**
 * 还原字符串 s 所能拼出的所有有效 IP 地址
 * @param {string} s - 只包含数字的字符串  例如 "25525511135"
 * @return {string[]} - 所有可能的有效 IP 地址
 */
function restoreIpAddresses(s) {
  const results = []


  /**
   * start - 当前字符串处理到的下标
   * segmentCount - 已经切分了多少段
   * path - 暂存已经切好的段，是一个数组，例如 ["255", "255"]
   */
  function backtrack(start, segmentCount, path) {
    if (segmentCount === 4) {
      // 说明已经切好了4段
      if (start === s.length) {
        // 说明字符串也刚好用完了
        results.push(path.join('.'))
      }
      return
    }


    // IP的每一段最多3个字符
    for (let length = 1; length <= 3; length++) {
      // 如果剩下的字符不足 length 个，直接 break 进行剪枝
      if (start + length > s.length) break


      // 代码来到这里，说明剩余字符是足够的
      const segment = s.substring(start, start + length)


      // 如果这一段的长度大于 1 并且该分段有前导 0，无效的，进行剪枝
      if (segment.length > 1 && segment[0] === '0') break


      // 接下来还需要检查数的范围
      // 如果超出了有效的数字范围，也需要进行剪枝
      const num = parseInt(segment, 10)
      if (num > 255) break


      // 代码来到这里，说明当前分段是有效的
      path.push(segment)
      backtrack(start + length, segmentCount + 1, path)
      path.pop()
    }
  }


  backtrack(0, 0, [])


  return results
}

-EOF-