分割回文串

题目描述

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

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

示例 2： 输入：s = “a”
输出：[["a"]]

思路&js代码

1、回溯

输入的视角（逗号选或不选）

假设每对相邻字符之间有个逗号，那么就看每个逗号是选还是不选。 也可以理解成：是否要把 s[i] 当成分割出的子串的最后一个字符。注意 s[n−1] 一定是最后一个字符，一定要选。

var isPalindrome = function(s, left, right) {
    while (left < right) {
        if (s.charAt(left++) !== s.charAt(right--)) {
            return false;
        }
    }
    return true;
}
 
var partition = function(s) {
    const n = s.length;
    const ans = [];
    const path = [];
 
    // 考虑 i 后面的逗号怎么选
    // start 表示当前这段回文子串的开始位置
    function dfs(i, start) {
        if (i === n) { // s 分割完毕
            ans.push(path.slice()); // 复制 path
            return;
        }
 
        // 不选 i 和 i+1 之间的逗号（i=n-1 时一定要选）
        if (i < n - 1) {
            // 考虑 i+1 后面的逗号怎么选
            dfs(i + 1, start);
        }
 
        // 选 i 和 i+1 之间的逗号（把 s[i] 作为子串的最后一个字符）
        if (isPalindrome(s, start, i)) {
            path.push(s.substring(start, i + 1));
            // 考虑 i+1 后面的逗号怎么选
            // start=i+1 表示下一个子串从 i+1 开始
            dfs(i + 1, i + 1);
            path.pop(); // 恢复现场
        }
    }
 
    dfs(0, 0);
    return ans;
};

2、回溯

答案的视角（枚举子串结束位置）

var isPalindrome = function(s, left, right) {
    while (left < right) {
        if (s.charAt(left++) !== s.charAt(right--)) {
            return false;
        }
    }
    return true;
}
 
var partition = function(s) {
    const n = s.length;
    const ans = [];
    const path = [];
 
    // 考虑 s[i] ~ s[n-1] 怎么分割
    function dfs(i) {
        if (i === n) { // s 分割完毕
            ans.push(path.slice()); // 复制 path
            return;
        }
        for (let j = i; j < n; j++) { // 枚举子串的结束位置
            if (isPalindrome(s, i, j)) {
                path.push(s.substring(i, j + 1)); // 分割！
                // 考虑剩余的 s[j+1] ~ s[n-1] 怎么分割
                dfs(j + 1);
                path.pop(); // 恢复现场
            }
        }
    }
 
    dfs(0);
    return ans;
};