力扣131 js实现

力扣131（分割回文串）的JavaScript实现

问题描述
给定字符串 s，将 s 分割成若干子串，使得每个子串都是回文串。返回所有可能的分割方案。

示例
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

方法思路

回溯法适合解决此类组合问题。通过递归探索所有可能的分割方式，并在每一步检查当前子串是否为回文，如果是则继续递归剩余部分。

代码实现

/
 * @param {string} s
 * @return {string[][]}
 */
const partition = function(s) {
    const result = [];
    const path = [];

    const isPalindrome = (str, left, right) => {
        while (left < right) {
            if (str[left] !== str[right]) return false;
            left++;
            right--;
        }
        return true;
    };

    const backtrack = (start) => {
        if (start === s.length) {
            result.push([...path]);
            return;
        }
        for (let end = start; end < s.length; end++) {
            if (isPalindrome(s, start, end)) {
                path.push(s.substring(start, end + 1));
                backtrack(end + 1);
                path.pop();
            }
        }
    };

    backtrack(0);
    return result;
};

代码解析

1. 初始化结果和路径
   result 存储所有合法的分割方案，path 记录当前递归路径下的分割子串。

2. 回文判断函数
   isPalindrome 通过双指针法验证子串 s[left...right] 是否为回文。

3. 回溯函数

   

   • 终止条件：当起始索引 start 达到字符串长度时，将当前 path 加入 result。
   • 递归过程：遍历可能的子串结束位置 end，若 s[start...end] 是回文，则将其加入 path 并递归处理剩余部分 end + 1，最后回溯移除当前子串。

复杂度分析

• 时间复杂度：O(N * 2^N)，最坏情况下所有子串均为回文，共有 2^N 种分割方式，每次判断回文需 O(N)。
• 空间复杂度：O(N)，递归栈深度最多为字符串长度。

此方法通过回溯高效枚举所有可能的分割方案，适合处理中等规模输入。