LeetCode上分割回文串，中等难度，记录下解题思路

参考官方题解，使用回溯+动态规划思路解题

需要判断截取的字符串是否为回文字符串，每次选取前i个元素进行切取，判断是否为回文，如果不是就排除这条分支，如果是就在剩余字符中继续取j元素进行切取

例如传入aab这个字符串
取i=1的时候，第一次截取a是回文，剩余字符串ab，再截取j =1获得a剩余b，继续截取为b，之后截取j=2可得ab不是回文，排除这条分支
所以在i=1的情况下能够截取到['a','a','b']这3个回文串
取i=2，截取可得aa，剩余字符串b，之后j=1可截取b
所以在i=2的情况下能够截取到['aa','b']这2个回文串
取i=3，截取可得aab，剩余字符串为空字符串，没有继续截取的必要，aab也不是一个回文字符串，所以排除这条分支
最后能够得到的结果[['a','a','b'],['aa','b']]

当不是回文串的时候就退到上一步用新的数据来计算的过程是个回溯求解的过程

可以分为以下2步
1.用回溯算法求取所有的子串
2.判断子串是否为回文串

用DP动态规划来求是否为回文串
相当于用一个二维表格来表示当前的字符串是否为回文字符串，还是以aab为例
dp[i][j]表示i~j范围内的元素是否为回文字符串

var partition = function (s) {
    // 结果数组
    const res = [];
   // 创建二维dp数组
    const dp = new Array(s.length).fill(0).map(() => new Array(s.length).fill(true));
  // 填充dp数组
    for (let j = 0; j < s.length; j++) {
        for (let i = 0; i <= j; i++) {
            if (i == j) {
                // 对角线上都是回文串
                dp[i][j] = true;
            } else if (j - i == 1 && s[i] == s[j]) {
                // 两个元素的情况，并且两个元素相等也是回文串
                dp[i][j] = true;
            } else if (j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]) {
                // 两个以上元素情况，并且首尾字符相同，以及剩下的元素是回文串
                dp[i][j] = true;
            } else {
                // 其他情况就不是回文串
                dp[i][j] = false;
            }
        }
    }
    // 回溯法计算
    function dfs(temp, start) {
        if (start == s.length) {
            res.push(temp.slice());
            return;
        }
        for (let i = start; i < s.length; i++) {
            // 查询dp是否为回文
            if (dp[start][i]) {
                // 是的情况就截取对应字符串
                temp.push(s.substring(start, i + 1));
                // 继续调用
                dfs(temp, i + 1);
                // 保存对应字符串
                temp.pop();
            }
        }
    }
    // 调用回溯算法
    dfs([], 0);
    // 返回结果
    return res;
};