# 0131. 分割回文串

### 题目地址(131. 分割回文串)

<https://leetcode-cn.com/problems/palindrome-partitioning/>

### 题目描述

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

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

示例:

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

```

### 前置知识

* 回溯法

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

这是一道求解所有可能性的题目， 这时候可以考虑使用回溯法。 回溯法解题的模板我们已经在很多题目中用过了， 这里就不多说了。大家可以结合其他几道题目加深一下理解。

这种题目其实有一个通用的解法，就是回溯法。网上也有大神给出了这种回溯法解题的[通用写法](https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-\(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning\))，这里的所有的解法使用通用方法解答。 除了这道题目还有很多其他题目可以用这种通用解法，具体的题目见后方相关题目部分。

这里我画了一个图：

![](https://p.ipic.vip/6g2gvx.jpg)

> 图是 [78.subsets](/leetcode-solution/medium/78.subsets.md)，都差不多，仅做参考。

### 关键点解析

* 回溯法

### 代码

* 语言支持：JS，Python3, CPP

JS Code:

```js
/*
 * @lc app=leetcode id=131 lang=javascript
 *
 * [131] Palindrome Partitioning
 */

function isPalindrom(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right && s[left] === s[right]) {
    left++;
    right--;
  }

  return left >= right;
}
function backtrack(s, list, tempList, start) {
  const sliced = s.slice(start);

  if (isPalindrom(sliced) && tempList.join("").length === s.length)
    list.push([...tempList]);

  for (let i = 0; i < sliced.length; i++) {
    const sub = sliced.slice(0, i + 1);
    if (isPalindrom(sub)) {
      tempList.push(sub);
    } else {
      continue;
    }
    backtrack(s, list, tempList, start + i + 1);
    tempList.pop();
  }
}
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  // "aab"
  // ["aa", "b"]
  // ["a", "a", "b"]
  const list = [];
  backtrack(s, list, [], 0);
  return list;
};
```

Python Code:

```python
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        """回溯法"""

        res = []

        def helper(s, tmp):
            """
            如果是空字符串，说明已经处理完毕
            否则逐个字符往前测试，判断是否是回文
            如果是，则处理剩余字符串，并将已经得到的列表作为参数
            """
            if not s:
                res.append(tmp)
            for i in range(1, len(s) + 1):
                if s[:i] == s[:i][::-1]:
                    helper(s[i:], tmp + [s[:i]])

        helper(s, [])
        return res
```

CPP Code:

```cpp
	class Solution {
private:
  vector<vector<string>> ans;
  vector<string> tmp;
  bool isPalindrome(string &s, int first, int last) {
    while (first < last && s[first] == s[last]) ++first, --last;
    return first >= last;
  }
  void dfs(string &s, int start) {
    if (start == s.size()) { ans.push_back(tmp); return; }
    for (int i = start; i < s.size(); ++i) {
      if (isPalindrome(s, start, i)) {
        tmp.push_back(s.substr(start, i - start + 1));
        dfs(s, i + 1);
        tmp.pop_back();
      }
    }
  }
public:
  vector<vector<string>> partition(string s) {
    dfs(s, 0);
    return ans;
  }
};
```

### 相关题目

* [39.combination-sum](/leetcode-solution/medium/39.combination-sum.md)
* [40.combination-sum-ii](/leetcode-solution/medium/40.combination-sum-ii.md)
* [46.permutations](/leetcode-solution/medium/46.permutations.md)
* [47.permutations-ii](/leetcode-solution/medium/47.permutations-ii.md)
* [78.subsets](/leetcode-solution/medium/78.subsets.md)
* [90.subsets-ii](/leetcode-solution/medium/90.subsets-ii.md)
* [113.path-sum-ii](/leetcode-solution/medium/113.path-sum-ii.md)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/131.palindrome-partitioning.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.