A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0
and 255
(inclusive) and cannot have leading zeros.
"0.1.2.201"
and "192.168.1.1"
are valid IP addresses, but "0.011.255.245"
, "192.168.1.312"
and "192.168@1.1"
are invalid IP addresses.Given a string s
containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s
. You are not allowed to reorder or remove any digits in s
. You may return the valid IP addresses in any order.
Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]
Example 3:
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Constraints:
1 <= s.length <= 20
s
consists of digits only.Solution
这道题目结合了具体的场景,会有一点难度。 每个组合可以是单独的 0,但是不能是前置 0 的多位数
我们可以想象有一个数组,然后有 4 个空位,我们要把 s 中的元素填充到这个数组里面去,比如第一个元素我们可以填写 255,第二个也可以填 255.
模拟这个过程。
我们可以来一个 segment 数组,然后 segmentid 代表数组的位置,然后 index 代表整个字符串的下标。每次我们都是从(index,index+3)的位置来选取。
只有当 segid == 5 以及 index == length 的时候才满足条件的 ip
var restoreIpAddresses = function(s) {
let result = [];
dfs(0, [], s, 0,result);
return result;
};
function isValidIPv4(str) {
if (str.length > 1 && str.charAt(0) === '0') return false; // 排除前导零的情况,除非是“0”
const num = parseInt(str);
return num <= 255; // 数字必须小于或等于255
}
function dfs(segid, segments, s, index,result) {
if (segid === 4 && index === s.length) {
result.push(segments.join('.')); // 当且仅当用完所有段且索引覆盖了整个字符串时,加入结果
return;
}
if (segid === 4 || index === s.length) return; // 提前终止不合理的递归路径
for (let len = 1; len <= 3 && index + len <= s.length; len++) { // 检查从1到3个字符的可能性
const sub = s.substring(index, index + len);
if (isValidIPv4(sub)) {
segments.push(sub);
dfs(segid + 1, segments, s, index + len,result);
segments.pop(); // 回溯,移除最后添加的段
}
}
}
var restoreIpAddresses = function(s) {
let result = [];
dfs(0,[],0,s,result);
return result;
}
function isVaild(str){
if(str.length > 1 && str.charAt(0) ==="0") return false;
const num = parseInt(str);
return num <= 255; // 数字必须小于或等于255
}
function dfs(segid, segments, index , s, result){
if(segid === 4 && index == s.length ){
result.push(segments.join("."));
return;
}
for (let i = 1 ;i <= 3 && i+index <= s.length; i++ ){
let sub = s.substring(index,index+i);
if (isVaild(sub)){
segments.push(sub);
dfs(segid+1,segments,index+i,s,result);
segments.pop();
}
}
}