93.Restore IP Addresses

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:

Input: s = "1111"
Output: ["1.1.1.1"]

Example 4:

Input: s = "010010"
Output: ["0.10.0.10","0.100.1.0"]

Example 5:

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

• 0 <= s.length <= 3000
• s consists of digits only.

Analyze

方法一: 遍历穷举法

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
  const arr = []
  for (let i = 1; i < 4; i++) {
    for (let j = i + 1; j < i + 5; j++) {
      for (let z = j + 1; z < j + 5; z++) {
        const a = s.slice(0, i)
        const b = s.slice(i, j)
        const c = s.slice(j, z)
        const d = s.slice(z, s.length)
        if (validate(a) && validate(b) && validate(c) && validate(d)) {
          arr.push(`${a}.${b}.${c}.${d}`)
        }
      }
    }
  }
  return arr
};

var validate = function (value) {
  if (value.length > 3 || value.length === 0 || +value > 255 || (value[0] === '0' && value.length > 1)) {
    return false
  }
  return true
}

方法二: 回溯法

回溯是一种思想。DFS 也是回溯思想的一种实践案例。回溯法本质是一种穷举的递归算法, 既然是递归, 它就需要有终止条件。

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

var backtracking = function(s, start, ipValue, res) {
  const splitIpNode = ipValue.split('.')
  const ipNode = splitIpNode.length
  // end condition
  for (let i = 0; i < ipNode; i++) {
    if (!isValid(splitIpNode[i])) return
  }
  if (ipValue.length === s.length + 3 && !ipValue.endsWith('.')) {
    // 比如 010010 存在两种相等的 case, 0100 + 1 + 0, 0100 + 10, 因此需要去重
    if (res.indexOf(ipValue) === -1) res.push(ipValue)
    return
  } else if (ipValue.length === s.length + 3 && ipValue.endsWith('.')) {
    return
  }

  for (let i = start + 1; i < start + 4; i++) {
    if (i >= s.length + 1) return
    const str = s.slice(start, i)
    const ipValueNew = ipNode <= 3 ? ipValue + str + '.' : ipValue + str
    backtracking(s, i, ipValueNew, res)
  }
}

// judge if the str value is valid for ip.
var isValid = function (value) {
  if (value.length > 3 || +value > 255 || (value[0] === '0' && value.length > 1)) {
    return false
  }
  return true
}

针对此题, 方法一相对方法二较为容易。