// 定义一个名为Solution的类
class Solution {
// 声明一个成员变量,用于存储所有满足条件的字符串子序列划分结果
List<List<String>> lists = new ArrayList<>();
// 声明一个成员变量,使用LinkedList实现的双端队列,用于临时存储当前的回文子串
Deque<String> deque = new LinkedList<>();
// 公共方法:partition,输入一个字符串s,返回所有可能的回文子序列划分结果
public List<List<String>> partition(String s) {
// 调用回溯法进行字符串划分处理
backTracking(s, 0);
// 返回所有找到的回文子序列划分集合
return lists;
}
// 私有辅助方法:backTracking,采用回溯算法遍历字符串s的所有可能划分
private void backTracking(String s, int startIndex) {
// 当起始位置大于等于字符串s的长度时,说明已经找到一组合法的回文子序列划分,将其添加到结果集中
if (startIndex >= s.length()) {
// 将deque中的回文子串列表复制一份添加到结果集lists中
lists.add(new ArrayList<>(deque));
return;
}
// 遍历从startIndex开始到字符串末尾的所有可能划分点
for (int i = startIndex; i < s.length(); i++) {
// 判断从startIndex到i(含)之间的子串是否为回文串
if (isPalindrome(s, startIndex, i)) {
// 若是回文串,则将该子串添加到deque中
String str = s.substring(startIndex, i + 1);
deque.addLast(str);
} else {
// 若不是回文串,则跳过本次循环继续尝试下一个子串
continue;
}
// 继续递归处理剩余部分字符串,同时确保不会重复处理已划分的部分
backTracking(s, i + 1);
// 回溯:在尝试完当前子串之后,将其从deque中移除,以便于尝试下一种可能的划分方式
deque.removeLast();
}
}
// 私有辅助方法:isPalindrome,用于判断给定索引范围内的子串是否为回文串
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)) {
// 如果发现有不相等的字符,则立即返回false,表示该子串不是回文串
return false;
}
}
// 所有字符都匹配成功,说明子串是回文串,返回true
return true;
}
}
上述代码定义了一个名为 Solution 的类,该类用于解决一个问题:将一个输入字符串 s 划分成多个子串,使得这些子串都是回文串。通过回溯算法,找出所有可能的回文子序列划分,并将结果以 List<List> 的形式返回。