93.复原IP地址

链接：93.复原IP地址
难度：Medium
标签：字符串、回溯
简介：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

题解 1 - typescript

• 编辑时间：2020-08-10
• 执行用时：88ms
• 内存消耗：37.3MB
• 编程语言：typescript
• 解法介绍：回溯+剪枝。

function restoreIpAddresses(s: string): string[] {
  const ans: string[] = [];
  find(s);
  return ans;
  function find(s: string, now = '', need = 4): void {
    if (need <= 0) return;
    for (let l = 1; l <= s.length; l++) {
      const subS = s.substr(0, l);
      if (Number(subS) > 255) return;
      const nextSubStr = s.substr(l);
      const nextNow = now.length === 0 ? subS : now + '.' + subS;
      if (need === 1 && nextSubStr.length === 0) ans.push(nextNow);
      else find(nextSubStr, nextNow, need - 1);
      if (s[0] === '0') return;
    }
  }
}

题解 2 - typescript

• 编辑时间：2021-07-21
• 执行用时：76ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：深度遍历。

function restoreIpAddresses(s: string): string[] {
  const n = s.length;
  const ans: string[] = [];
  find();
  return ans;
  function find(index = 0, list: (string | number)[] = []): void {
    if (list.length === 4 && index !== n) return;
    if (index === n) {
      list.length === 4 && ans.push(list.join('.'));
      return;
    }
    if (s[index] === '0') {
      list.push(0);
      find(index + 1, list);
      list.pop();
      return;
    }
    const num1 = getNum(index);
    let num2!: number;
    let num3!: number;
    list.push(num1);
    find(index + 1, list);
    list.pop();
    if (index + 1 < n) {
      num2 = num1 * 10 + getNum(index + 1);
      list.push(num2);
      find(index + 2, list);
      list.pop();
    }
    if (index + 2 < n) {
      num3 = num2 * 10 + getNum(index + 2);
      if (num3 <= 255) {
        list.push(num3);
        find(index + 3, list);
        list.pop();
      }
    }
  }
  function getNum(index: number) {
    return s[index].codePointAt(0)! - '0'.codePointAt(0)!;
  }
}