93. 复原 IP 地址 - 力扣（LeetCode）

发布：2021年9月18日21:26:11

问题描述及示例

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 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 地址。

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

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

示例 3：
输入：s = “1111”
输出：[“1.1.1.1”]

示例 4：
输入：s = “010010”
输出：[“0.10.0.10”,“0.100.1.0”]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

提示：
0 <= s.length <= 3000
s 仅由数字组成

我的题解（回溯）

这应该是我在LeetCode碰到的第二个有关回溯的题目了，之前写过一个相关的题解博客：

参考：【算法-LeetCode】46. 全排列（回溯算法初体验）_赖念安的博客-CSDN博客

在我看来，其实回溯就是递归的一种应用，往往用在一些需要穷举所有可能的情况，而回溯和一般的递归的区别，我觉得就是所谓的“回溯”操作，也就是：当一层递归完成后，把程序中的某些变量（这些变量往往是全局的）恢复到递归前的状态。回溯操作的典型结构如下：

let globalVar;
let globalVar2;
...
globalVar2++;
operateA(); // 在operateA之前，globalVar的状态是X；在operateA之后，globalVar的状态变为Y
backtracking(params);
operateB(); // 在operateB之前，globalVar的状态是Y；在operateB之后，globalVar的状态恢复为X
globalVar2--;
...

也就是说，operateA() 和 operateB() 的操作效果刚好是相互抵消的。比如数组的 push() 和 pop() 方法。这就是回溯算法最精髓的部分：把状态恢复到递归前。

详细解释请看下方注释：

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
  if (s.length < 4 || s.length > 12) {
    return [];
  }
  let results = [];
  let ip = [];
  backtracking(s, 0);
  return results;

  function backtracking(str, start) {
    // 加上下面这个if判断，也可以优化性能
    if(ip.length > 4) {
      return;
    }
    if (start === str.length) {
      if (ip.length === 4) {
        results.push(ip.join('.'));
      }
      return;
    }
    for (let i = start; i < str.length; i++) {
      let segment = str.substring(start, i + 1);
      if (!isValidSegment(segment)) {
        break;
      }
      ip.push(segment);
      backtracking(str, i + 1);
      ip.pop();
    }
  }
  function isValidSegment(str) {
    if (!str || str.length > 3) {
      return false;
    }
    if (str[0] === '0') {
      return str.length > 1 ? false : true;
    }
    return Number(str) <= 255 ? true : false;
  }
};


提交记录
执行结果：通过
147 / 147 个通过测试用例
执行用时：76 ms, 在所有 JavaScript 提交中击败了67.63%的用户
内存消耗：39.3 MB, 在所有 JavaScript 提交中击败了55.32%的用户
时间：2021/09/18 21:35

官方题解

更新：2021年7月29日18:43:21

因为我考虑到著作权归属问题，所以【官方题解】部分我不再粘贴具体的代码了，可到下方的链接中查看。

更新：2021年9月18日21:35:40

参考：复原IP地址 - 复原 IP 地址 - 力扣（LeetCode）

【更新结束】

有关参考

更新：2021年9月18日21:34:22
参考：【算法-LeetCode】46. 全排列（回溯算法初体验）_赖念安的博客-CSDN博客
参考：String.prototype.substring() - JavaScript | MDN