93. Restore IP Addresses
93. Restore IP Addresses
题目
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.
- For example,
"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 intos. 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 <= 20sconsists of digits only.
题目大意
有效 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 中的任何数字。你可以按 任何 顺序返回答案。
解题思路
这道题可以使用回溯法来解决。IP 地址由 4 个数字组成，每个数字的范围是 0 到 255。回溯法的基本思路是尝试每一种可能性，当得到一个满足条件的组合时，继续搜索下一个可能的数字。
使用一个递归函数，每次从字符串中截取一个数字（可以是 1、2、3 位数字），将该数字加入当前的 IP 地址组合中，然后递归处理剩余的部分。
在递归函数中，需要注意一些剪枝的条件，比如：
- 如果当前截取的数字超过了字符串的长度，结束递归。
- 如果当前截取的数字是以 0 开头的多位数，应该跳过，因为 IP 地址中不允许有前导零。
- 如果当前截取的数字大于 255，也应该跳过。
如果得到的 IP 地址组合正好有 4 个数字，并且字符串被完全截取完毕，就将当前的组合加入结果集。
具体步骤：
- 初始化一个数组
res用于存放结果。 - 定义一个递归函数
backtrack，接受参数start表示当前截取的位置，track表示当前已经得到的 IP 地址组合。 - 在
backtrack函数中，判断终止条件：- 如果
track中超过了 4 个数字，直接返回。 - 如果
track中已经有 4 个数字，且start刚好等于字符串的长度，将当前track加入res。
- 如果
- 在循环中，每次截取 1、2、3 位数字，判断是否满足条件（不超过字符串长度，不以 0 开头的多位数，小于等于 255），满足条件则递归调用
backtrack。 - 最后，在主函数中返回结果数组
res。
代码
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function (s) {
let res = [];
let track = [];
const isValid = (str) => {
if ((str.length > 1 && str[0] == '0') || Number(str) > 255) {
return false;
}
return true;
};
const backtrack = (start) => {
if (track.length > 4) return;
if (start == s.length && track.length == 4) {
res.push(track.join('.'));
return;
}
for (let i = start; i < s.length; i++) {
const str = s.substring(start, i + 1);
if (isValid(str)) {
track.push(str);
backtrack(i + 1);
track.pop();
}
}
};
backtrack(0);
return res;
};