【算法-LeetCode】93. 复原 IP 地址(回溯;递归)

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

上一篇:软件供应商是网络安全致命弱点?数据显示93%公司因第三方面临安全漏洞


下一篇:LeetCode 93. 复原IP地址