复原IP地址

[louzhedong]

习题

出处：LeetCode 算法第93题

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

示例:

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

思路

典型的深度遍历，遍历所有的可能

解答

/**
 * @param {string} s
 * @return {string[]}
 */
function restoreIpAddresses(s) {
  const res = [];
  dfs([], 0);
  return res;

  function dfs(prefix, idx) {
    if (prefix.length === 4 && idx === s.length) {
      res.push(prefix.join('.'));
      return;
    }

    if (prefix.length === 4 || idx === s.length) {
      return;
    }

    for (let r = idx; r < s.length; r++) {
      if (r !== idx && s[idx] === '0') return;

      const num = parseInt(s.slice(idx, r + 1));
      if (num > 255) {
        return;
      }
      prefix.push(num);
      dfs(prefix, r + 1);
      prefix.pop();
    }
  }
}