6. 分割回文串（131）

一、题目内容 中等

给你一个字符串 s，请你将 _s _分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串

示例1：

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

示例2：

输入：s = “a” 输出：[[“a”]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

  二、解题思路

  本题这涉及到两个关键问题：

1. 切割问题，有不同的切割方式
2. 判断回文

我们来分析一下切割，其实切割问题类似组合问题。
例如对于字符串 abcdef：

• 组合问题：选取一个 a 之后，在 bcdef 中再去选取第二个，选取 b 之后在 cdef 中在选组第三个…..。
• 切割问题：切割一个 a 之后，在 bcdef 中再去切割第二段，切割 b 之后在 cdef 中在切割第三段…..。

所以切割问题，也可以抽象为一棵树形结构，如图：

三、具体代码

/**
 * 判断字符串是否是回文字符串
 */
const isPalindrome = (str, start, end) => {
  for (let i = start, j = end; i < j; i++, j--) {
    if (str[i] !== str[j]) return false
  }
  return true
}
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  const path = []
  const res = []
  const len = s.length
  const backTracking = (start) => {
    if (start >= len) {
      res.push(path.map(i => i))
      return
    }
    for (let i = start; i < len; i++) {
      if (!isPalindrome(s, start, i)) continue  // 如果截取的字符串片段不是回文的，那么没必要继续深度查找了
      const str = s.substr(start, i - start + 1)
      path.push(str)
      backTracking(i + 1)
      path.pop()
    }
  }
  backTracking(0)
  return res
};

四、其他解法