# 131.Palindrome Partitioning

**131.Palindrome Partitioning**

> 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 难度：Medium 返回 s 所有可能的分割方案。

示例:

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

直观解决方法：递归。 因为所有子数组都是回文，所以从第一个开始，找到一个回文后，将剩下的子串找出所有的可能性组合，最后再合并即可。 代码如下:

```
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n=s.length(),cnt=0;
        vector<vector<string>> res;
        vector<string> ret;
        if (n == 1)
        {
            ret.push_back(s);
            res.push_back(ret);
            return res;
        }

        vector<vector<string>> tmp;
        for(int i=1;i<n;i++)
        {
            string fir=s.substr(0,i);
            if(ispalind(fir))
            {
                tmp=merge(fir,partition(s.substr(i,n-i)));
                res.insert(res.end(),tmp.begin(),tmp.end());
            }
        }
        if(ispalind(s))
        {
            ret.push_back(s);
            res.push_back(ret);
        }
        return res;
        
    }
    vector<vector<string>> merge(string a, vector<vector<string>>b)
    {
        vector<vector<string>> res;

        for(int i=0;i<b.size();i++)
        {
            vector<string>tmp;
            tmp.push_back(a);
            tmp.insert(tmp.end(),b[i].begin(),b[i].end());
            res.push_back(tmp);
        }
        return res;
    }
    bool ispalind(string s)
    {
        int n=s.length();
        for(int i=0;i<n/2;i++)
            if(s[i]!=s[n-i-1]) return false;
        return true;
    }
};
```

定义了一个函数来判断是否是回文，另一个函数用来将第一个子串和剩下的回文向量合并，最后判断整个字符串是否是回文。\
但这样并不高效。因为运算时间比较长。 提交结果的一个比较好的示例如下：

```
class Solution {
    vector<vector<string>> res;
    
    void DFS(string& s, int begin, vector<string>& t){
        if(begin>=s.length())
            res.push_back(t);
        else{
            t.push_back("");
            for(int end=begin;end<s.length();end++)
                if(isParl(s, begin, end)){
                    t[t.size()-1] = s.substr(begin, end-begin+1);
                    DFS(s, end+1, t);
                }
            t.pop_back();
        }
    }
    
    
    bool isParl(string& s, int begin, int end){
// 可以用DP存储加速
        while(begin<end){
            if(s[begin]!=s[end])
                return false;
            begin++;
            end--;
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
        vector<string> t;
        DFS(s, 0, t);
        return res;
    }
};
```

采用深度优先搜索DFS，也是递归调用完成。


---

# 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://dfine.gitbook.io/leetcode/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.