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;
    }
};