131.分割回文串

解题思路：

使用深度优先搜索，一旦搜索到回文字符串，那么就进入递归，并且递归中从上一次搜索的下一个位置开始搜索。具体见代码。

class Solution {
    
    vector<vector<string>> ret;
public:
    //判断是否是回文字符串
    bool calc(const string& s){
    
        int i=0,j=s.size()-1;
        while(i<j){
    
            if(s[i]!=s[j]) return false;
            ++i;
            --j;
        }
        return true;
    }

    vector<vector<string>> partition(string s) {
    
        vector<string> vec;
        dfs(s,vec,0);
        return ret;
    }

    void dfs(const string& s,vector<string>& vec,int start){
    
        //假如能够递归到这一步说明字符串s已经分割完毕，且都是回文字符串
        if(start>=s.size())
        {
    
            ret.push_back(vec);
            return;
        }

        string tmp;
        for(int i=start;i<s.size();++i){
    
            tmp+=s[i];
            //看是否是回文串，是的话进入递归
            if(calc(tmp)){
    
                vec.push_back(tmp);
                dfs(s,vec,i+1);
                vec.pop_back();
            }
        }
    }
};