Appearance
93. 复原 IP 地址
题目描述
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
- 输入： s = "25525511135"
- 输出：
["255.255.11.135","255.255.111.35"]
示例 2：
- 输入： s = "0000"
- 输出：
["0.0.0.0"]
示例 3：
- 输入： s = "101023"
- 输出：
["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20s仅由数字组成
难度： Medium
题解代码
javascript
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
const ret = []
backTrack(s, [], ret)
return ret
};
function backTrack (s, path, ret) {
if (path.length === 4) {
if (s.length) return
const v = path.join('.')
if (isValid(v) && !ret.includes(v)) return ret.push(v)
}
for (let i = 1; i < 4; i++) {
if (s.length > 3 * (4 - path.length) || (s.length < 4 - path.length)) continue
path.push(s.slice(0, i))
s = s.slice(i)
backTrack(s, path, ret)
s = path.pop() + s
}
}
function isValid (s) {
return !(s.split('.').some(item => (Number(item) > 255 || (item[0] === '0' && item.length > 1))))
}