分割回文串.md

分割回文串

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

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

示例:

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

回溯+动态规划解法

框架是基本的回溯，主要就是判断循环体的跳过逻辑，即判断s字符中[i, j]是否为回文串

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
  const res = []
  // 二维数组，dp[i][j]指字符串[i, j]是否为回文
  const dp = Array(s.length).fill(1).map(() => [])
  /**
   * @param target-已选择的回文数组
   * @param start-当前遍历的下标
   */
  const dfs = (target, start) => {
    if (start === s.length) {
      res.push([...target])
      return
    }
    for (let i = start; i < s.length; i++) {
      // 单个字符是回文
      if (i === start) {
        dp[i][start] = true
      }
      // 前后两个相同的是回文
      else if (i === start + 1 && s[i] === s[start]) {
        dp[start][i] = true
      }
      // aba回文能推出xabax也是回文
      else if (s[i] === s[start] && dp[start+1][i-1]) {
        dp[start][i] = true
      }
      // 当前的不是回文，跳过
      if (!dp[start][i]) continue
      target.push(s.substring(start, i+1))
      dfs(target, i + 1)
      target.pop()
    }
  }
  dfs([], 0)
  return res
};