【算法-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” 和 “[email protected]” 是 無效 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