## 题目地址(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://tva1.sinaimg.cn/large/007S8ZIlly1ghlty0bvj4j31190u0jw4.jpg)

> 图是 [78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/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](./39.combination-sum.md)
- [40.combination-sum-ii](./40.combination-sum-ii.md)
- [46.permutations](./46.permutations.md)
- [47.permutations-ii](./47.permutations-ii.md)
- [78.subsets](./78.subsets.md)
- [90.subsets-ii](./90.subsets-ii.md)
- [113.path-sum-ii](./113.path-sum-ii.md)