小学生都能看懂的题解 | #数字字符串转化成IP地址#
问题描述
我们需要把一个只包含数字的字符串转换成所有可能的IP地址。IP地址的格式是这样的：x.x.x.x，其中 x 是0到255之间的数字。例如，字符串 25525522135 可以转换成 255.255.22.135 和 255.255.221.35。
解决方案步骤
-
分割字符串：
- IP地址由四部分组成，我们需要从字符串中分出这四部分。
-
检查每一部分：
- 每一部分（x）必须是0到255之间的数字，并且不能以0开头（比如01、02不是有效的部分）。
-
生成所有可能的组合：
- 我们可以尝试从字符串的每个位置开始，分割出长度为1、2或3的部分，看看能否组成一个有效的IP地址。
-
递归（重复做同样的事）：
- 我们用一种叫“递归”的方法来不断尝试不同的分割方法，直到找到所有可能的有效IP地址。
代码解释
以下是每个部分的简单解释：
import java.util.ArrayList;
import java.util.List;
public class IPAddressGenerator {
- 我们导入了需要的工具（比如可以用来存储结果的列表）。
- 创建了一个名为
IPAddressGenerator的类。
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
backtrack(result, s, 0, "", 0);
return result;
}
restoreIpAddresses是主方法，它接收一个字符串s，然后调用另一个方法backtrack来找到所有可能的IP地址。- 我们创建了一个空的列表
result来存放找到的所有有效IP地址。
private void backtrack(List<String> result, String s, int index, String currentIp, int segmentCount) {
backtrack是一个帮助的方法，它会尝试分割字符串，找到有效的IP地址。- 它的参数包括：
result（结果列表），s（输入字符串），index（当前处理的位置），currentIp（当前形成的IP地址），segmentCount（当前已经分出的部分数量）。
if (segmentCount == 4 && index == s.length()) {
result.add(currentIp);
return;
}
- 这里我们检查如果已经分了4个部分，并且字符串也完全用完了，就把这个有效的IP地址加入结果列表。
if (segmentCount > 4 || index >= s.length()) {
return;
}
- 如果分出的部分超过4个，或者字符串还没有结束，就直接返回，结束这个分割尝试。
for (int length = 1; length <= 3; length++) {
if (index + length > s.length()) {
break;
}
- 这里我们尝试每一部分的长度，可以是1位、2位或3位。
- 如果超过了字符串的长度，就停止尝试。
String segment = s.substring(index, index + length);
- 从字符串中提取当前长度的部分。
if (isValid(segment)) {
backtrack(result, s, index + length, currentIp + (segmentCount == 0 ? "" : ".") + segment, segmentCount + 1);
}
- 如果这部分是有效的，就继续递归，尝试分割剩下的部分。
currentIp + (segmentCount == 0 ? "" : ".") + segment是在当前IP后面加上这个部分。
private boolean isValid(String segment) {
if (segment.length() > 1 && segment.charAt(0) == '0') {
return false; // Leading zero
}
int value = Integer.parseInt(segment);
return value >= 0 && value <= 255;
}
isValid方法检查每一部分是否有效：长度超过1且以0开头就不合法，数字必须在0到255之间。
完整代码
import java.util.ArrayList;
import java.util.List;
public class IPAddressGenerator {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
backtrack(result, s, 0, "", 0);
return result;
}
private void backtrack(List<String> result, String s, int index, String currentIp, int segmentCount) {
if (segmentCount == 4 && index == s.length()) {
result.add(currentIp);
return;
}
if (segmentCount > 4 || index >= s.length()) {
return;
}
for (int length = 1; length <= 3; length++) {
if (index + length > s.length()) {
break;
}
String segment = s.substring(index, index + length);
if (isValid(segment)) {
backtrack(result, s, index + length, currentIp + (segmentCount == 0 ? "" : ".") + segment, segmentCount + 1);
}
}
}
private boolean isValid(String segment) {
if (segment.length() > 1 && segment.charAt(0) == '0') {
return false;
}
int value = Integer.parseInt(segment);
return value >= 0 && value <= 255;
}
}
希望这篇文章对你有帮助👍。
#题解#小学生都能看懂的算法 文章被收录于专栏
主要面向小白的算法文章。以小学生都能看懂为目标而编写，顺便巩固下自己。
