分割回文串

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

  • 输入：s = “aab”

  • 输出：[[“a”,”a”,”b”],[“aa”,”b”]]

  • 输入：s = “a”

  • 输出：[[“a”]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const partition = function(s) {
    const res = [], path = [], len = s.length;
    backtracking(0);
    return res;
    function backtracking(i) {
        if(i >= len) {
            res.push(Array.from(path));
            return;
        }
        for(let j = i; j < len; j++) {
            if(!isPalindrome(s, i, j)) continue;
            path.push(s.slice(i, j + 1));
            backtracking(j + 1);
            path.pop();
        }
    }
};

const isPalindrome = (s, l, r) => {
    for (let i = l, j = r; i < j; i++, j--) {
        if(s[i] !== s[j]) return false;
    }
    return true;
}