61.分割回文串(学习)
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串
。返回 s 所有可能的分割方案。
示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
解析：
一、变量定义
1.result：一个数组，用于存储所有可能的分割方案。
2.current：一个数组，用于在回溯过程中构建当前的分割方案。
二、辅助函数：isPalindrome
1.这个函数检查传入的字符串str是否是回文串。它通过比较字符串的首尾字符，并逐步向中心移动，来验证整个字符串是否对称。
三、回溯函数：backtrack
1.这是解决问题的核心函数。它使用回溯算法来尝试所有可能的分割方式。
2.基准情况：如果start等于字符串s的长度，说明已经遍历完整个字符串，此时将current（当前的分割方案）添加到result中。
3.循环遍历：从start开始，遍历字符串s的剩余部分。对于每个位置i，截取从start到i（包含i）的子串。
4.检查回文：使用isPalindrome函数检查截取的子串是否是回文串。
5.添加并继续：如果是回文串，则将其添加到current中，并递归调用backtrack(i + 1)来继续处理剩余的字符串。
6.撤销选择：回溯结束后，需要从current中移除最后添加的子串，以便尝试其他可能的分割方式。
四、调用回溯函数
1.在partition函数的末尾，通过调用backtrack(0)开始回溯过程，从字符串的起始位置开始尝试所有可能的分割。
var partition = function (s) {
const result = [];
const current = [];
// 辅助函数：检查子串是否是回文串
function isPalindrome(str) {
let left = 0;
let right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) {
return false;
}
left++;
right--;
}
return true;
}
// 回溯函数
function backtrack(start) {
// 如果已经遍历完整个字符串，则将当前分割方案添加到结果中
if (start === s.length) {
result.push([...current]);
return;
}
for (let i = start; i < s.length; i++) {
// 截取从start到i的子串
const substring = s.substring(start, i + 1);
// 检查子串是否是回文串
if (isPalindrome(substring)) {
// 如果是回文串，则将其添加到当前分割方案中
current.push(substring);
// 继续向后回溯
backtrack(i + 1);
// 回溯结束，撤销选择
current.pop();
}
}
}
backtrack(0);
return result;
};```