Wednesday, December 3, 2014

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"]
  ]


Initial attempt:
class Solution {
public:
    bool palindrome(string s)  
    {
        int len = s.size();
        for (int i=0;i<len/2; i++)
        {
            if (s[i]!=s[len-i])
              return false;
        }
        return true;
    }
   
    void helper( int i, string s, vector<string> &p, vector<vector<string>> &ret)
    {
        int slen = s.size();
        if (i==slen-1&&flag)
        {
            ret.push_back(p);
        }
       
   
        for (int k=i; k<slen; k++)
        {
            if (palindrome(s.substr(0,k)))
               {
                   p.push_back(s.substr(0,k));       //Got stuck

               }
        }
        i++;
    }
   
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        int len=s.size();
        if (len==0) return ret;
       
        vector<string> p;
        helper(0,s,p,ret);
        return ret;
    }
};

No comments:

Post a Comment