Given a string containing only digits, restore it by returning all possible valid IP address combinations. A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points. 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。 **示例：** ~~~ 输入： “25525511135” 输出： ["255.255.11.135", "255.255.111.35"] ~~~ ``` /** * @param {string} s * @return {string[]} */ var restoreIpAddresses = function(s) { let res = []; if(s.length<4 || s.length>12) return res;//判断边界 dfs(res,s,"",0); return res; function dfs(res,s,sub,index){ if(index == 4 && s.length == 0) res.push(sub.substring(1)); if(index == 4 || s.length == 0) return; dfs(res,s.substring(1),sub+"."+s.substring(0,1),index+1);//一位数 if(s.charAt(0) !='0' && s.length > 1){//两位数 dfs(res,s.substring(2),sub + "." + s.substring(0,2),index+1); if(s.length > 2 && parseInt(s.substring(0,3)) <= 255){//三位数 dfs(res,s.substring(3),sub+"."+s.substring(0,3),index+1); } } } }; ``` ``` var restoreIpAddresses = function(str) { // 判断最大边界 if(str.length > 12) return [] // 保存所有符合条件的IP地址 let r = [] // 分四步递归处理ip分段 let search = (cur, sub) => { // 边界条件 if (cur.length === 4 && cur.join('') === str) { // 过滤 001 010等情况 if(cur[3].length > 1 && cur[3][0] == 0){ return false } r.push(cur.join('.')) } else { // 正常的处理过程 for (let i = 0, len = Math.min(3, sub.length), tmp; i < len; i++) { tmp = sub.substr(0, i + 1) // 过滤 001 010等情况 if (tmp.length > 1 && tmp[0] == 0) { return false } if (tmp < 256) { search(cur.concat([tmp]), sub.substr(i + 1)) } } } } search([], str) return r } ```