131.分割回文串

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例 1:

1
2
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

1
2
输入:s = "a"
输出:[["a"]]

Solution

可以根据答案视角的模版来写,如果是回文就添加并且回溯,不是就下一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
// ans 用来存储所有可能的回文分割结果
private final List<List<String>> ans = new ArrayList<>();
// path 用来记录当前递归路径上选择的字符串片段
private final List<String> path = new ArrayList<>();
// s 存储输入的字符串
private String s;

// 公共方法,输入是一个字符串,输出是这个字符串的所有回文分割方案
public List<List<String>> partition(String s) {
this.s = s; // 将输入的字符串存储到类的成员变量s中,供整个类使用
dfs(0); // 从字符串的第一个字符开始深度优先搜索
return ans; // 返回包含所有回文分割方案的列表
}

// 判断字符串s中从索引left到right的子串是否是回文
private boolean isPalindrome(int left, int right) {
while (left < right) // 使用双指针技术从两头向中间检查
if (s.charAt(left++) != s.charAt(right--)) // 如果两边字符不同,则不是回文
return false;
return true; // 否则是回文
}

// 使用深度优先搜索(DFS)生成所有可能的回文分割
private void dfs(int i) {
if (i == s.length()) { // 如果索引i等于字符串长度,说明已经到达字符串末尾
ans.add(new ArrayList<>(path)); // 将当前路径(即当前构建的分割方案)复制并添加到结果列表中
return;
}
for (int j = i; j < s.length(); ++j) { // 从索引i开始,枚举可能结束的位置j
if (isPalindrome(i, j)) { // 检查从i到j的子串是否是回文
path.add(s.substring(i, j + 1)); // 如果是回文,则将其添加到当前路径中
dfs(j + 1); // 递归调用dfs,从j+1开始继续搜索
path.remove(path.size() - 1); // 撤销选择,即从path中移除最后一个元素,恢复到选择前的状态
}
}
}
}