Constfunction partition(s: string): string[][] {
const n = s.length;
const ans: string[][] = [];
const path: string[] = [];
// 考虑>=i的下标为起始位置的子串该如何分割
function dfs(i: number) {
if (i === n) {
ans.push([...path]);
return;
}
// 枚举子串的结束位置
for (let j = i; j < n; j++) {
const str = s.slice(i, j + 1);
// 如果是回文串
if (str.split('').reverse().join('') === str) {
path.push(str);
dfs(j + 1); // 当前层完成后，考虑以>=j+1为起始位置的子串该如何分割
path.pop(); // 在本层下一次循环前恢复现场腾出对应位置放新的尝试
}
}
}
dfs(0);
return ans;
};
131.分割回文串
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是 回文串 。返回s所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：
s = "aab"输出：
[["a","a","b"],["aa","b"]]示例 2：
输入：
s = "a"输出：
[["a"]]提示：
1 <= s.length <= 16s仅由小写英文字母组成