复原IP地址
题目
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
枚举法
IP地址有四段组成，每一段都是0至255的整数。使用枚举法将字符串拆分为四个长度介于1和3之间的字符串，再校验每一段是否有效。
举个例子，给定字符串010010。将其拆分组合以深度为4的树展示：
从根节点到第四层节点之间的路径就是一种将字符串分为四段三位以内整数的分法。
代码实现
package io.github.rscai.leetcode.bytedance.string;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution1044A {
public List<String> restoreIpAddresses(String s) {
List<List<String>> addresses = restore(s, 4);
List<String> validAddresses = new ArrayList<>();
for (List<String> address : addresses) {
boolean isValid = true;
for (String i : address) {
if (i.startsWith("0") && Integer.valueOf(i) != 0) {
isValid = false;
break;
}
if (i.length() > 1 && Integer.valueOf(i) == 0) {
isValid = false;
break;
}
if (Integer.valueOf(i) > 255) {
isValid = false;
break;
}
}
if (isValid) {
validAddresses.add(String
.format("%s.%s.%s.%s", address.get(0), address.get(1), address.get(2), address.get(3)));
}
}
return validAddresses;
}
private List<List<String>> restore(String s, int count) {
if (s.length() == 0) {
return Collections.emptyList();
}
if (count == 1 && s.length() > 3) {
return Collections.emptyList();
}
if (count == 1) {
return Collections.singletonList(Collections.singletonList(s));
}
List<List<String>> results = new ArrayList<>();
for (int i = 1; i < Math.min(4, s.length()); i++) {
String e = s.substring(0, i);
String remainStr = s.substring(i, s.length());
for (List<String> remain : restore(remainStr, count - 1)) {
List<String> merged = new ArrayList<>();
merged.add(e);
merged.addAll(remain);
results.add(merged);
}
}
return results;
}
}
首先，罗列出从字符串中解出四个三位以内整数的所有组合。
然后，过泸不符合要求的组合。IP地址每一段都是0至255之间的整数，且除了0之外所有整数的最高位都不是0。
最后，再把所有地址格式成题目要求的格式。
从字符串中解出四个整数所有组合使用递归方式实现。先从字符串中解出一个整数，
再从剩余字符串解出其余的整数，并拼接在一起
递归的终止条件有：
- 剩余字符串为空
- 其余整数个数为1且剩余字符串长度大于3
- 剩余整数个数为1
复杂度分析
时间复杂度
IP中四段整数最大的组合数量为。因为输入字符串的长度上限固定为12，所以时间复杂度为。
空间复杂度
空间复杂度为。
回溯法
上述枚举法可以通过回溯法优化。罗列字符串拆解为四个整数的组合可以建模为深度优先遍历树。当四整数组合的一部不满足IP地址规格约束时，就可以判定整个组合不满足约束。映射到树遍历模型，就是当发现从根到叶子节点路径的一部份不满足解的要求，则以这段路径为一部份其它所有路径都是不满足解要求的。
举个例子，给定字符串010010。当第一个整数解出为01时，就可以判定01不是一个正确的整数形式（除了0之外的整数，最高位都不是0）。所以01以下的子树都无需遍历了。
代码实现
package io.github.rscai.leetcode.bytedance.string;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution1044B {
public List<String> restoreIpAddresses(String s) {
List<List<String>> addresses = restore(s, 4);
List<String> formatedAddresses = new ArrayList<>();
for (List<String> address : addresses) {
formatedAddresses.add(String
.format("%s.%s.%s.%s", address.get(0), address.get(1), address.get(2), address.get(3)));
}
return formatedAddresses;
}
private List<List<String>> restore(String s, int count) {
if (s.length() == 0) {
return Collections.emptyList();
}
if (count == 1 && s.length() > 3) {
return Collections.emptyList();
}
if (count == 1) {
if (isValid(s)) {
return Collections.singletonList(Collections.singletonList(s));
} else {
return Collections.emptyList();
}
}
List<List<String>> results = new ArrayList<>();
for (int i = 1; i < Math.min(4, s.length()); i++) {
String e = s.substring(0, i);
if (!isValid(e)) {
continue;
}
String remainStr = s.substring(i, s.length());
if (remainStr.length() < count - 1) {
continue;
}
if (remainStr.length() > 3 * (count - 1)) {
continue;
}
for (List<String> remain : restore(remainStr, count - 1)) {
List<String> merged = new ArrayList<>();
merged.add(e);
merged.addAll(remain);
results.add(merged);
}
}
return results;
}
private boolean isValid(String e) {
if (e.startsWith("0") && Integer.valueOf(e) != 0) {
return false;
}
if (e.length() > 1 && Integer.valueOf(e) == 0) {
return false;
}
if (Integer.valueOf(e) > 255) {
return false;
}
return true;
}
}
回溯法的实现大体与枚举法相同，只是在递归调用之前，判断讫今为止的部份解是否已违反了解的约束。若是，则无需再探索以不合格部份解为共同部份的解。
复杂度分析
时间复杂度
因输入数据量是常数，所以时间复杂度为常数。
空间复杂度
空间复杂度为。