目录
131.分割回文串
中等
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
其实切割问题类似组合问题。
例如对于字符串abcdef：
- 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
- 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。
解读题意：每存在一种方式可将字符串分割为回文子串时，就将分割好的回文子串存到一个List集合中，再存入List结果集合中
// Solution类，包含了分割字符串为回文子串的方法
class Solution {
// 用于存储所有可能的分割方案，每个方案是一个字符串列表
List<List<String>> lists = new ArrayList<>();
// 用于临时存储当前分割方案的回文子串
List<String> substring = new ArrayList<>();
// public方法，接收一个字符串s，返回所有可能的回文子串分割方案
public List<List<String>> partition(String s) {
// 调用回溯方法开始分割字符串
backTracking(s, 0);
// 返回所有分割方案
return lists;
}
// 私有方法，使用回溯法分割字符串
private void backTracking(String s, int startIndex) {
// 如果起始位置超过了字符串的长度，说明已经找到了一个完整的分割方案
if (startIndex == s.length()) {
// 将当前方案添加到结果列表中（注意这里要添加deque的副本）
lists.add(new ArrayList<>(substring));
return;
}
// 遍历从起始位置到字符串末尾的每个位置
for (int i = startIndex; i < s.length(); i++) {
// 检查从startIndex到i的子串是否是回文的
if (isPalindrome(s, startIndex, i)) {
// 如果是回文子串，则添加到当前方案中
String str = s.substring(startIndex, i + 1);
substring.add(str);
} else {
// 如果不是回文子串，则跳过当前位置，继续向后检查
continue;
}
// 回溯，将起始位置后移一位，继续寻找下一个回文子串
backTracking(s, i + 1);
// 回溯，移除当前方案中的最后一个回文子串，尝试其他可能性
substring.removeLast();
}
}
// 私有辅助方法，用于判断一个子串是否是回文的
private boolean isPalindrome(String s, int startIndex, int end) {
// 使用双指针法，一个指针从起始位置开始，另一个指针从结束位置开始
for (int i = startIndex, j = end; i < j; i++, j--) {
// 如果两个指针指向的字符不相等，则子串不是回文的
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
// 如果所有字符都相等，则子串是回文的
return true;
}
}93.复原IP地址
中等
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 无效 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仅由数字组成
class Solution {
List<String> result = new ArrayList<>(); // 用于存放所有可能的IP地址
StringBuilder builder = new StringBuilder(); // 用于构建当前的IP地址
public List<String> restoreIpAddresses(String s) {
backtracking(s, 0, 0); // 从字符串的开头开始回溯，还没有任何段被选择
return result; // 返回所有可能的IP地址列表
}
public void backtracking(String s, int begin, int numCount) {
// 如果已经遍历完整个字符串，并且已经选择了4个段，说明找到了一个可能的IP地址
if (begin == s.length() && numCount == 4) {
result.add(builder.toString());
return;
}
// 如果已经遍历完整个字符串，或者已经选择了4个段，但字符串还没有遍历完，说明当前路径不可能构成IP地址
if (begin == s.length() || numCount == 4) {
return;
}
// 遍历可能的段结束位置
for (int i = begin; i < s.length(); i++) {
// 检查当前子串是否可以作为一个IP地址的段
if (isvalid(s, begin, i)) {
// 将当前段添加到构建器中
builder.append(s.substring(begin, i + 1));
numCount++; // 已选段数加一
// 如果当前选择的段数小于4，说明还需要继续选择段，因此添加一个点作为分隔符
if (numCount < 4) {
builder.append(".");
}
// 继续回溯，选择下一个段
backtracking(s, i + 1, numCount);
// 回溯，删除当前段以及分隔的点（如果存在）
// 注意：删除的是当前段的最后一个字符到构建器末尾的所有字符，即整个段和可能存在的点
//从开始位置+加入的点的位置开始
builder.delete(begin + numCount - 1, builder.length());
numCount--; // 已选段数减一
} else {
// 如果当前子串不能作为一个IP地址的段，则跳出循环，尝试下一个可能的开始位置
//如果不是一段有几种情况，长度大于一且0开头，数字大于255，长度大于3，往下遍历没有意义
break;
}
}
}
//这里的begin和end是左闭右闭的区间
public boolean isvalid(String s, int begin, int end) {
// 如果开始位置大于结束位置，说明子串为空，不是有效的段
if (begin > end) {
return false;
}
// 如果子串表示的整数大于255，不是有效的段
if (Integer.parseInt(s.substring(begin, end + 1)) > 255) {
return false;
}
// 如果子串长度大于3，不是有效的段（IP地址段最多3位数字）
if (end - begin + 1 > 3) {
return false;
}
// 如果子串以0开头且长度大于1（除了单个0的情况），不是有效的段
if (s.charAt(begin) == '0' && end - begin > 0) {
return false;
}
// 如果以上条件都不满足，说明子串是一个有效的段
return true;
}
}
