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"]
  ]
C++:
01 class Solution {
02 public:
03     bool isPalindrome(int i, int j, string s)
04     {
05         if(i>=j)
06             return true;
07         if(s[i]!=s[j])
08             return false;
09         return isPalindrome(i+1,j1,s);
10     }
11 
12     vector<string> appendString(vector<string> list, string s)
13     {
14         list.push_back(s);
15         return list;
16     }
17 
18     vector<vector<string>> partition(string s) {
19         // Start typing your C/C++ solution below
20         // DO NOT write int main() function
21         vector<vector<string>> init;
22         vector<vector<vector<string>>> array;
23         vector<string> tmp;
24         init.push_back(tmp);
25         array.push_back(init);
26         for(int i=0;i<s.size();i++)
27         {
28             vector<vector<string>> newitem;
29             for(int j=0;j<=i;j++)
30             {
31                 if(isPalindrome(j,i,s))
32                 {
33                     for(int t=0;t<array[j].size();t++)
34                     {
35                         newitem.push_back
36                           (appendString(array[j][t],
37                                         s.substr(j,ij+1)));
38                     }
39                 }
40             }
41             array.push_back(newitem);
42         }
43         return array[s.size()];
44     }
45 };
Advertisements
This entry was posted in Array and linked list, Dynamic programming, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s