# \[131]\[中等]\[DFS]\[回溯]\[动态规划] 分割回文串

## 题目描述

[131. 分割回文串](https://leetcode-cn.com/problems/palindrome-partitioning/)

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

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

示例:

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

## 解题思路

将一个字符串分割成若干个回文子串, 可以列举出第一个子串的分割方法, 然后问题转换成剩余子串的分割方法, 因此是一种类似于树结构的DFS, 在枚举出的当前子串不是回文串时剪枝.

由于需要列出所有可能的分割方案, 因此需要加上回溯方法, 在找到一种方案后不能停止, 去掉本层搜索的痕迹, 回溯到上一层继续遍历, 把所有的可能都走一遍.

另外一点是如何快速地判断子串是否是回文串, 最简单的方法是判断`s == s[::-1]`是否成立. 另外还可以使用动态规划预先计算好每个位置i到位置j之间的子串是否是回文串, 用f(i, j)表示, 为`True`说明是回文串, 而计算f(i, j)只需要依赖f(i+1, j-1), 如果f(i+1, j-1)且s\[i]==s\[j], f(i, j)则为True, 否则为False.

这是一个只需要计算上三角缓存矩阵的问题, 每个位置的值至于它的左下角有关, 因此遍历方法需要特别注意, 具体解释可以参考: [\[5\]\[中等\]\[动态规划\] 最长回文子串](/garnet/suan-fa/dong-tai-gui-hua/5-zui-chang-hui-wen-zi-chuan.md).

```python
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.s = s
        self.n = len(s)
        if self.n == 0:
            return []

        self.results = []
        self.cache = [[False] * self.n for _ in range(self.n)]
        for i in range(self.n - 1, -1, -1):
            for j in range(self.n - 1, i - 1, -1):
                if j - i > 1 and s[i] == s[j]:
                    self.cache[i][j] = self.cache[i + 1][j - 1]
                elif j - i == 1:
                    self.cache[i][j] = s[i] == s[j]
                elif j == i:
                    self.cache[i][j] = True

        self.dfs(0, [])
        return self.results

    def dfs(self, i, path):
        if i == self.n:
            self.results.append(path[:])
            return path

        for j in range(i, self.n):
            if self.cache[i][j]:
                path.append(self.s[i:j + 1])
                path = self.dfs(j + 1, path)
                path.pop()
        return path
```

## 参考资料

* [回溯法：思路与模板](https://leetcode-cn.com/problems/palindrome-partitioning/solution/hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dfs/131-fen-ge-hui-wen-chuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.