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 <= 20`
- `s` 仅由数字组成
难度： 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))))
}