有效 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
中的任何数字。你可以按 任何 顺序返回答案。
示例 1:
输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]
示例 2:
输入:s = "0000"
输出:["0.0.0.0"]
示例 3:
输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示:
1 <= s.length <= 20
s
仅由数字组成
解法1 DFS+回溯
首先明确一下合法的IP地址的条件:
- 一个IP地址有四个分段;
- 每个分段表示的数值小于等于 255 255 255
- 分段除了表示为 0 0 0 的情况以外,其他情况第一个数字不能为 0 0 0
所以判断分段合法性的代码如下:
stoi(sa) <= 255 && (sa == "0" || seg[0] != '0')
下面的代码,从当前位置的字符开始,往后依次查看长度为 1 , 2 , 3 1,2,3 1,2,3 的字符串,判断它们是否合法,合法则加入IP分段数组,并继续递归。递归回溯后,从IP分段数组中弹出当前分段即可。直到扫描完整个字符串为止,我们判断IP分段数组中是否只有4个分段,是则将分段以 .
连接起来,加入答案中。
为了提升算法的效率,我们可以做一下剪枝:
- s s s 如果是合法IP地址,则长度最大只能到 12 12 12 、最小必须 ≥ 4 \ge 4 ≥4 ,题目范围
0 <= s.length <= 3000
这么大,可能是来迷惑人的吧…… - 递归过程中,如果当前IP分段数组的长度超过了 4 4 4 ,则直接返回,说明之前有分段太小了。
class Solution {
private:
vector<string> ans;
void dfs(const string &s, int idx, vector<string>& addrs) {
if (addrs.size() > 4) return; // 分段超过4个则剪枝
if (idx >= s.size()) {
if (addrs.size() == 4)
ans.push_back(addrs[0] + "." + addrs[1] + "." + addrs[2] + "." + addrs[3]);
return;
}
for (int len = 1; len <= 3; ++len) {
if (idx + len > s.size()) break;
string sa = s.substr(idx, len);
if (stoi(sa) > 255 || (sa != "0" && sa[0] == '0')) break;
addrs.push_back(sa);
dfs(s, idx + len, addrs);
addrs.pop_back();
}
}
public:
vector<string> restoreIpAddresses(string s) {
if (s.size() < 4 || s.size() > 12) return {};
vector<string> temp;
dfs(s, 0, temp);
return ans;
}
};
复杂度分析:我们用 SEG_COUNT = 4 \text{SEG\_COUNT} = 4 SEG_COUNT=4 表示IP地址的段数。
- 时间复杂度: O ( 3 SEG_COUNT × n ) O(3^\text{SEG\_COUNT} \times n) O(3SEG_COUNT×n) 。由于IP地址的每一段的位数不会超过 3 3 3 ,因此在递归的每一层,我们最多只会深入到下一层的 3 3 3 种情况。由于 SEG_COUNT = 4 \text{SEG\_COUNT} = 4 SEG_COUNT=4 ,对应着递归的最大层数,所以递归本身的时间复杂度为 O ( 3 SEG_COUNT ) O(3^\text{SEG\_COUNT}) O(3SEG_COUNT) 。如果我们复原出了一种满足题目要求的IP地址,那么需要 O ( ∣ s ∣ ) = O ( n ) O(|s|) = O(n) O(∣s∣)=O(n) 的时间将其加入答案数组中,因此总时间复杂度为 O ( 3 SEG_COUNT × n ) O(3^\text{SEG\_COUNT} \times n) O(3SEG_COUNT×n) 。
- 空间复杂度: O ( n ) O(n) O(n) 。 n n n 为 s s s 的长度,但不超过合法IP地址的最大长度。这里不考虑存储答案数组的空间。
解法2 四重循环暴力求解
写的很爽,代码很优雅:
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> ret = new ArrayList<>();
StringBuilder ip = new StringBuilder();
for (int a = 1; a < 4; ++a) {
for (int b = 1; b < 4; ++b) {
for (int c = 1; c < 4; ++c) {
for (int d = 1; d < 4; ++d) {
if (a + b + c + d == s.length()) {
int n1 = Integer.parseInt(s.substring(0, a)); // "010" -> 10(int)
int n2 = Integer.parseInt(s.substring(a, a + b));
int n3 = Integer.parseInt(s.substring(a + b, a + b + c));
int n4 = Integer.parseInt(s.substring(a + b + c));
if (n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255) {
ip.append(n1).append('.').append(n2).append('.').append(n3).append('.').append(n4);
if (ip.length() == s.length() + 3) ret.add(ip.toString()); // 有前导零的会被过滤掉
ip.delete(0, ip.length());
}
}
}
}
}
}
return ret;
}
}
复杂度分析:
- 时间复杂度: O ( 3 4 ) O(3^4) O(34)
- 空间复杂度: O ( n ) O(n) O(n)