93-复原IP地址.md

题目描述

复原 IP 地址

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

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

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。

示例 1：

• 输入：s = "25525511135"
• 输出：["255.255.11.135","255.255.111.35"]

分类

中等 回溯

思路

思路 1

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
  if (s.length > 12) {
    return [];
  }
  const res = [];
  const tempRes = [];
  function backTrack(index) {
    if (tempRes.length === 4 && index === s.length) {
      res.push(tempRes.join("."));
      return;
    }
    let str = "";
    for (let i = index; i < index + 3 && i < s.length; i++) {
      str += s[i];
      if (judgeIp(str)) {
        tempRes.push(str);
        backTrack(i + 1);
        tempRes.pop();
      }
    }
  }
  backTrack(0, "");
  return res;
};
function judgeIp(str) {
  if ((str[0] === "0" && str !== "0") || parseInt(str) > 255) return false;
  return true;
}

• 问题分析
  • 题目的限制条件：将字符串完全分割为 4 段，每段长度为 1-3 位，值在 0-255 之间，且每段首位不能为 0
  • 回溯函数backTrack作用：入参为起始分割位置，从起始位置开始分割，如果该值符合条件则继续调用backTrack，对下一段进行分割。
  • 回溯终止条件：当前分割段数为 4 段且所有段字符长度总和为题目输入字符长度（即完全分割）
  • 单次回溯可能性：因为长度限制为 1-3 位，所以从index开始，往后再至多两位。
  • 符合 IP 规则条件判断，不符合条件情况：
    • 字符串首位为 0 且长度不止一位 (str[0] === '0' && str !== '0')
    • 数字大于 255 (parseInt(str) > 255)