使用 JavaScript 解答 LeetCode 第 93 题,复原 IP 地址,中等难度。

题目

原题链接

本题目是 LeetCode 题库第 93 题,由此访问。

题目描述

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

解题

AC 样例

 /**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
  const result = [];
  // 边界判定和处理
  if(s.length > 12 || s.length < 4) return result;
  restore(s, [], result);
  return result;
};

const restore = (text, currentResult, result) => {
  // 递归结束边界条件
  if(currentResult.length == 4 && text.length == 0) { 
    result.push(Array.from(currentResult).join('.'));
    return ;
  }

  for (let i = 1; i < 4; i++) {
    if(text.length < i) continue;
    // 获取当前地址段字符串
    const str = text.slice(0,i);
    // 检查和排除首字符为 0 的情况下的边界条件
    if ((str.length > 1 && str[0] == '0') || Number(str) > 255) continue;
    /* 
      将地址段入栈,进行递归检查
      如地址段为优解则保留,否则回溯至上个数据
    */ 
    currentResult.push(str);
    restore(text.slice(i), currentResult, result);
    currentResult.pop();
  }
}

解题思路

根据题目要求,将一个只包含数字的字符串分割成可能的 IP 地址格式,首先可以排除当字符串长度小于 4 或大于 12 的情形,在这些情况下不可能得到答案,故返回空数组。

在长度检查无误后,开始尝试划分字符串。当字符串长度为 4 时,可以直接将其分为最小的四个子串,作为一组答案返回。其他长度字符串需要多次尝试划分。

从字符串头部开始,取 1-3 位数进行分割,而后将分割后的字符串进行递归。分割后剩余字符串长度为 0 时停止递归。在这一过程中,对分割得到的字符串做合规检查,要求其首字符不能为 0,三个字符长度的字符串转为数字时不能大于 255。

如在一次递归过程中,有这样一组字串符合条件,即:所有分割的子串均合规,同时在分为四个字串后没有多余和缺少的字符。这样的一组字串将作为返回值返回。如在一次递归过程中,分割的字串未能合规,则退出递归。

这里采用的算法是 回溯法,即通过递归对当前情况进行试探,如果可行便进一步试探,如不可行即回退后变更路径再试探。