分割回文串

[Aras-ax]

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

解答

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    let res = [];

    if (s === null || s.length === 0) {
        return res;
    }

    let len = s.length,
        arr = [];

    function palindrome(s, start) {
        if (start === len) {
            res.push([...arr]);
            return;
        }
        for (let i = start; i < len; i++) {
            let curStr = s.substring(start, i + 1);
            if (isPalindrome(s, start, i)) {
                arr.push(curStr);
                palindrome(s, i + 1);
                arr.pop();
            }
        }
    }

    palindrome(s, 0);
    return res;
}


/**
 * 是否是回文
 */
function isPalindrome(s, left, right) {
    while (left < right && s[left] === s[right]) {
        left++;
        right--;
    }
    return left >= right;
}