93 Restore IP Addresses

1. Question

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example: Given"25525511135",
return["255.255.11.135", "255.255.111.35"]. (Order does not matter)

2. Implementation

(1) Backtracking
1
class Solution {
2
public List<String> restoreIpAddresses(String s) {
3
List<String> res = new ArrayList<>();
4
5
if (s == null || s.length() == 0) {
6
return res;
7
}
8
9
List<String> parts = new ArrayList<>();
10
getIpAddresses(s, 0, parts, res);
11
return res;
12
}
13
14
public void getIpAddresses(String s, int start, List<String> parts, List<String> res) {
15
if (start == s.length() && parts.size() == 4) {
16
res.add(parts.get(0) + "." + parts.get(1) + "." + parts.get(2) + "." + parts.get(3));
17
return;
18
}
19
20
// ip地址由4部分组成,每个部分有1-3个数位组成,4 - parts.size()表示我们需要的ip地址剩余的部分,s.length() - start表示目前string剩下的长度
21
// 以下两种情况我们会停止搜索
22
// 1. 如果ip地址每个部分由1个数位组成,那么我们需要的ip地址剩余的部分至少为4 - parts.size(), 如果4 - parts.size()大于string剩下的长度,说明string剩余的长度无法构成由1个数位组成4个部分的ip地址
23
// 2. 如果ip地址每个部分由3个数位组成,那么我们需要的ip地址剩余部分最多为3 * (4 - parts.size()), 如果3 * (4 - parts.size())小于剩余string剩下的长度,说明string无法完全用来构成ip地址
24
if (4 - parts.size() > s.length() - start || 4 - parts.size() < (s.length() - start) / 3) {
25
return;
26
}
27
28
for (int i = start; i < start + 3 && i < s.length(); i++) {
29
String part = s.substring(start, i + 1);
30
31
if (isValid(part)) {
32
parts.add(part);
33
getIpAddresses(s, i + 1, parts, res);
34
parts.remove(parts.size() - 1);
35
}
36
}
37
}
38
39
public boolean isValid(String s) {
40
if (s.startsWith("0") && s.length() > 1) {
41
return false;
42
}
43
int num = Integer.parseInt(s);
44
return num >= 0 && num <= 255;
45
}
46
}
Copied!

3. Time & Space Complexity

Backtracking: 时间复杂度O() ?, 空间复杂度O() ?