// 定义一个名为Solution的类

class Solution {

// 声明一个成员变量，用于存储所有满足条件的字符串子序列划分结果

List> lists = new ArrayList<>();

// 声明一个成员变量，使用LinkedList实现的双端队列，用于临时存储当前的回文子串

Deque deque = new LinkedList<>();

// 公共方法：partition，输入一个字符串s，返回所有可能的回文子序列划分结果

public List> 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 的形式返回。

参考文章

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。