131 分割回文串.md

131 分割回文串

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

示例 1：

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

示例 2：

**输入：**s = "a" **输出：[["a"]]

回溯 枚举字符串结束位置

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 = [];

    function dfs(i) {
        if (i === n) {
            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));
                dfs(j + 1);
                path.pop(); // 恢复现场
            }
        }
    }

    dfs(0);
    return ans;
};