131.分割回文串 中等

问题：

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

示例 1：

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

示例 2：

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

回答：

var partition = function(s) {
    const n = s.length;
  const result = [];
  const path = [];

  // dp[i][j] 表示 s[i..j] 是否是回文
  const dp = Array.from({ length: n }, () => Array(n).fill(false));

  // 从短到长递推
  for (let j = 0; j < n; j++) {
    for (let i = 0; i <= j; i++) {
      if (s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
      }
    }
  }

  function backtrack(start) {
    if (start === n) {
      result.push([...path]);
      return;
    }
    for (let end = start; end < n; end++) {
      if (dp[start][end]) {
        path.push(s.slice(start, end + 1));
        backtrack(end + 1);
        path.pop();
      }
    }
  }

  backtrack(0);
  return result;
};