93. 复原 IP 地址

93. 复原 IP 地址open in new window

🟠 🔖 字符串 回溯 🔗 力扣open in new window LeetCodeopen in new window

题目

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 <= 20
s consists 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。

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。递归栈最多会有 4 层，是常数级别的；每个字符都可能成为 IP 的一个部分，需要检查 O(n) 个可能的子串。
空间复杂度：O(1)(不考虑结果数组的存储空间)，递归栈最多会有 4 层，是常数级别的。

代码

/**
 * @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;
};

93. 复原 IP 地址

# 93. 复原 IP 地址open in new window

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

93. 复原 IP 地址open in new window

题目

题目大意

解题思路

复杂度分析

代码

相关题目