lintcode---分割回文串

题目描述：

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

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

样例：

给出 s = “aab”，返回

[
  ["aa", "b"],
  ["a", "a", "b"]
]
           

思路讲解：我的第一想法就是深搜，利用递归，每次我们都可以循环判断还没有判断的字符串是否可以构成回文串的长度，这里需要注意的一点就是，我们这里讲每一次我们都是将一种情况保存在一个字符串中，并以‘，’来分割，这样是为了避免我们用数组时，需要删除的麻烦。

代码详解：

class Solution {
public:
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    vector<vector<string>> partition(string &s) {
        // write your code here
        vector<string>strres;
        string flag="";
        dfs(strres,,s,flag);
        printstr(strres);
        cout<<strres.size()<<endl;
        vector<vector<string>>res(strres.size());

        cout<<strres.size()<<endl;
        for(int i=;i<strres.size();i++){
            string tmp=strres[i].substr(,strres[i].length()-);
            cout<<tmp<<endl;
            string ss="";
            for(int j=;j<tmp.length();j++){//将每一种的情况分割出来
                if(tmp[j]!=','){
                    ss=ss+tmp[j];
                }else{
                    res[i].push_back(ss);
                    ss="";
                }
                if(j==tmp.length()-){
                    res[i].push_back(ss);
                }
            }
        }
        return res;
    }
    void dfs(vector<string>&res,int index,string s,string &flag){//深搜
        if(index==s.length()){
            res.push_back(flag);
        }else if(index<s.length()){
            int len=s.length();
            for(int i=;i<=len-index;i++){
                string temp=s.substr(index,i);
                if(judge_is_pal(temp)){
                    string tt=flag+","+temp;
                    dfs(res,index+i,s,tt);
                }
            }
        }

    }
    bool judge_is_pal(string ss){//判断一个字符串是否是回文字符串
        int len=ss.length();
        for(int i=;i<=len/;i++){
            if(ss[i]!=ss[len-i-]){
                return false;
            }
        }
        return true;
    }
    void printstr(vector<string>res){
        for(int i=;i<res.size();i++){
            cout<<res[i]<<" ";
        }
        cout<<endl;
    }
};