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 } ```