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
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if (s == null || s.length() == 0) {
return res;
}
List<String> parts = new ArrayList<>();
getIpAddresses(s, 0, parts, res);
return res;
}
public void getIpAddresses(String s, int start, List<String> parts, List<String> res) {
if (start == s.length() && parts.size() == 4) {
res.add(parts.get(0) + "." + parts.get(1) + "." + parts.get(2) + "." + parts.get(3));
return;
}
// ip地址由4部分组成,每个部分有1-3个数位组成,4 - parts.size()表示我们需要的ip地址剩余的部分,s.length() - start表示目前string剩下的长度
// 以下两种情况我们会停止搜索
// 1. 如果ip地址每个部分由1个数位组成,那么我们需要的ip地址剩余的部分至少为4 - parts.size(), 如果4 - parts.size()大于string剩下的长度,说明string剩余的长度无法构成由1个数位组成4个部分的ip地址
// 2. 如果ip地址每个部分由3个数位组成,那么我们需要的ip地址剩余部分最多为3 * (4 - parts.size()), 如果3 * (4 - parts.size())小于剩余string剩下的长度,说明string无法完全用来构成ip地址
if (4 - parts.size() > s.length() - start || 4 - parts.size() < (s.length() - start) / 3) {
return;
}
for (int i = start; i < start + 3 && i < s.length(); i++) {
String part = s.substring(start, i + 1);
if (isValid(part)) {
parts.add(part);
getIpAddresses(s, i + 1, parts, res);
parts.remove(parts.size() - 1);
}
}
}
public boolean isValid(String s) {
if (s.startsWith("0") && s.length() > 1) {
return false;
}
int num = Integer.parseInt(s);
return num >= 0 && num <= 255;
}
}

3. Time & Space Complexity

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