问题描述
LeetCode 93. 复原 IP 地址 (opens in a new tab)，难度中等。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"[email protected]"是 无效 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 <= 20s仅由数字组成
题解
回溯
解题思路：主要使用回溯的思路，定义变量 current 保存当前构建的 IP 地址片段。递归终止条件：已经构建了 4 段并且用完所有字符；否则尝试取 1-3 个字符作为一个 IP 片段并检查其有效性。
Solution.java
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
// 如果字符串为空，长度为小于 4 或者大于 12，直接返回结果
if (s == null || s.length() < 4 || s.length() > 12) {
return result;
}
backtrack(result, new ArrayList<>(), s, 0);
return result;
}
// 回溯函数
public void backtrack(List<String> result, List<String> current, String s, int start) {
// 如果当前 current 保存了 4 段并且正好使用完所有字符，则加入结果集
if (current.size() == 4) {
if (start == s.length()) {
result.add(String.join(".", current));
}
return;
}
// 取 1-3 个数字
for (int i = 1; i <= 3; ++i) {
if (start + i > s.length()) {
break;
}
// 递归检查其有效性
String segment = s.substring(start, start + i);
if (isValid(segment)) {
current.add(segment);
backtrack(result, current, s, start + i);
current.remove(current.size() - 1);
}
}
}
public boolean isValid(String segment) {
// 如果长度大于 1 并且以 0 开头，则是无效 IP
if (segment.length() > 1 && segment.startsWith("0")) return false;
// 判断是否在 0-255 之间
int num = Integer.parseInt(segment);
return num >= 0 && num <= 255;
}
}