给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
抛砖引玉
思路
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
let len = s.length,
result = [],
IP = '';
for (let a = 1; a < 4; ++a) {
for (let b = 1; b < 4; ++b) {
for (let c = 1; c < 4; ++c) {
if (a + b + c < len) {
let A = +s.substring(0, a),
B = +s.substring(a, a + b),
C = +s.substring(a + b, a + b + c),
D = +s.substring(a + b + c);
if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {
IP = A + '.' + B + '.' + C + '.' + D;
if (IP.length === len + 3) result.push(IP);
}
}
}
}
}
return result;
}
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
let dp = Array(4),
result = [];
const dfs = (s, ip, start) => {
// 匹配4段
if (ip === 4 && start === s.length) {
// 字符匹配完成
if (start === s.length) {
result.push(dp.join('.'));
}
return;
}
// 匹配完字符未匹配4段,匹配失败结束
if (start === s.length) return;
// 遇到开始匹配位置为0,0,独立存在则直接开始下一次匹配
if (s.charAt(start) === '0') {
dp[ip] = 0;
dfs(s, ip + 1, start + 1);
}
// 枚举每一种可能性并递归
let num = 0;
for (let i = start; i < s.length; ++i) {
num = num * 10 + (s.charAt(i) - '0');
if (num > 0 && num <= 255) {
dp[ip] = num;
dfs(s, ip + 1, i + 1);
} else {
break;
}
}
}
dfs(s, 0, 0);
return result;
};