leetcode[131]Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

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

class Solution {
public:
void judge(string s,bool ** &T)
{
    if(s.empty())return;
    for(int i=0;i<s.length();i++)
    {
        T[i][i]=true;
        int left=i-1,right=i;
        while(left>=0&&right<s.length()&&s[left]==s[right])
        {
            T[left--][right++]=true;
        }
        left=i-1,right=i+1;
        while(left>=0&&right<s.length()&&s[left]==s[right])
        {
            T[left--][right++]=true;
        }
    }
}
void solve(vector<vector<string>> &res,vector<string> tmp,string s,bool ** &T,int pos)
{
    if(pos==s.length())
    {
        res.push_back(tmp);
        return;
    }
    for(int i=pos;i<s.length();i++)
    {
        if(!(s.substr(pos,i-pos+1)).empty()&&T[pos][i])
        {
            tmp.push_back(s.substr(pos,i-pos+1));
            solve(res,tmp,s,T,i+1);
            tmp.pop_back();
        }
    }
}
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        if(s.empty())return res;
        vector<string> tmp;
        int n=s.length();
        bool **T=new bool*[n];
        for(int i=0;i<n;i++)
        {
            T[i]=new bool[n];
            for(int j=0;j<n;j++)
            T[i][j]=false;
        }
        judge(s,T);
        solve(res,tmp,s,T,0);
        return res;
    }
/**
bool valid(string s)
{
    int i=0;
    int j=s.size()-1;
    while(i<j)
    {
        if(s[i++]==s[j--])continue;
        else return false;
    }
    return true;
}
void find(vector<vector<string>> &res, vector<string> tmp,string s)
{
    if(s.empty())
    {
        if(!tmp.empty())res.push_back(tmp);
        return;
    }
    for(int i=1;i<=s.size();i++)
    {
        string str=s.substr(0,i);
        if(!str.empty()&&valid(str))
        {
            tmp.push_back(str);
            find(res,tmp,s.substr(i));
            tmp.pop_back();
        }
    }
}
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        if(s.empty())return res;
        vector<string> tmp;
        find(res,tmp,s);
        return res;
    }
*/
};