分割回文串（JS实现）

1 题目
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: “aab”
输出:
[
[“aa”,“b”],
[“a”,“a”,“b”]
]

2 思路
这道题的主要思路还是用构造一棵树+剪枝的方法，来获取所有满足需求的子串组合，其实还有优化的地方，比如判断回文串是可以使用动态规划缓存结果

3代码
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
const result = [];

d([],s);

return result;

function d(arr, leftStr) {
if (leftStr.length === 0) result.push(arr);

for (let i=1;i<=leftStr.length;i++) { //遍历可能的子串，长度从1开始
let substr = leftStr.substr(0,i);
if (isPStr(substr)) {
let temp = arr.slice();
temp.push(substr);
d(temp, leftStr.slice(i));
}
}
}

function isPStr(str) {
if (str.length === 1) return true;

let low = 0;
let high = str.length – 1;

while(low <= high) {
if (str[low] !== str[high]) {
return false;
}

low++;
high–;
}

return true;
}
};