石河子市网站建设_网站建设公司_Banner设计_seo优化

题目：
有效 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~3 个字符作为一个段。
检查这个段是否合法：
数值在 0~255 之间
如果长度大于 1，不能以 “0” 开头
如果合法，加入当前路径，继续递归。
当找到 4 段并且用完了所有字符时，保存结果。

具体代码：

/** * @param {string} s * @return {string[]} */varrestoreIpAddresses=function(s){// res: 存储所有合法的 IP 地址结果// path: 存储当前正在构建的 IP 地址的四个段constres=[]letpath=[]// 从字符串的第一个字符开始回溯back(0)returnresfunctionback(i){// 获取当前已经分割的段数constlen=path.length// 剪枝：如果已经超过 4 段，直接返回（IP 地址只能是 4 段）if(len>4)return// 终止条件：已经有 4 段，并且用完了所有字符// 说明找到了一个合法的 IP 地址if(len===4&&i===s.length){// 将四个段用点连接起来，加入结果集res.push(path.join("."))return}// 从当前位置 i 开始，尝试截取不同长度的子串作为一段for(letj=i;j<s.length;j++){// 截取从 i 到 j 的子串作为当前段conststr=s.slice(i,j+1)// 剪枝条件1：段长度不能超过 3，数值不能超过 255// 注意：这里使用 break 而不是 continue，因为再往后截取只会更长或更大if(str.length>3||+str>255)break// 剪枝条件2：如果段长度大于 1，且以 '0' 开头，不合法（前导零）if(str.length>1&&str[0]==='0')break// 当前段合法，加入路径path.push(str)// 递归处理剩余部分，从 j+1 开始back(j+1)// 回溯：撤销选择，尝试其他长度的分割path.pop()}}};