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
}

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