1. 题目描述
给定一个只包含数字的字符串,复原它并返回所有可能的 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 地址。
示例 1:
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]
示例 2:
输入:s = "0000"
输出:["0.0.0.0"]
示例 3:
输入:s = "1111"
输出:["1.1.1.1"]
示例 4:
输入:s = "010010"
输出:["0.10.0.10","0.100.1.0"]
示例 5:
输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示:
0 <= s.length <= 3000
-
2. 解题思路
对于这道题目,我们可以使用深度优先遍历,然后进行剪枝回溯操作,直到组合成为一个ip地址,详见代码注释。**
3. 代码实现
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
const res = []
const dfs = (subRes, start) => {
// 如果当前已经有四个字段,并且整个字符串已经用完了,那么就直接将当前的数组元素拼接成一个ip地址并加入结果数组中
if(subRes.length === 4 && start === s.length){
res.push(subRes.join('.'))
return
}
// 如果当前已有四个字段,但是没有用完整个字符串,直接剪枝,返回进行回溯
if(subRes.length === 4 && start < s.length) return
// 列举出三种长度的选择,来对字符串进行分割
for(let len = 1; len <= 3; len++){
// 如果当前的位置加上len要越界,就直接舍去
if(start + len - 1 >= s.length) return
// 如果当前分割的长度为2或者3时,排除掉以0开头的情况
if(len !== 1 && s[start] === '0') return
// 截取出当前的片段
const str = s.substring(start, start + len)
// 如果当前的片段的长度为3,并且值大于255,那么就直接舍弃
if(len === 3 && +str > 255) return
// 做出选择,将截取出来的片段加入subRes中
subRes.push(str)
// 基于当前的选择,继续选择
dfs(subRes, start + len)
// 上一次的递归结束后,撤销最后的选择,继续下一轮的迭代
subRes.pop()
}
}
dfs([], 0)
return res
};
4. 提交结果