Palindrome Partitioning

 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.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

 class Solution {

public:

    vector<vector<string> > ans;

    bool check(string s)

    {

       int i=0,j=s.size()-1;

        while(i<j)

        {

            if(s[i]!=s[j])

                return false;

            ++i,--j;

        }

        return true;

    }

    void partition(string s,vector<string> &res)

    {

        if(s.size()==0)

                    ans.push_back(res);

        for(int k=0;k<s.size();++k)

        {

            if(check(s.substr(0,k+1)))

            {

                res.push_back(s.substr(0,k+1));

                partition(s.substr(k+1),res);

                res.pop_back();

            }

        }

    }

    vector<vector<string>> partition(string s) 

    {

        vector<string> res;

        partition(s,res); 

        return ans;

    }

};