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. 提交结果
若有收获，就点个赞吧
0 人点赞
