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;
};```