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"] ]
递归求解所有划分可能～
1 class Solution {
2 public:
3 vector< vector<string> > ans;
4
5 bool IsPalindrome(string s, int start, int end){
6 if(start==end)
7 return true;
8 int i=start, j=end;
9 while(i<j){
10 if(s[i]!=s[j])
11 return false;
12 i++;
13 j--;
14 }
15 return true;
16 }
17 void recursivePar(string s, int start, vector<string> par){
18
19 if(start == s.length()){
20 ans.push_back(par);
21 return ;
22 }
23 for(int i=start; i<s.length(); i++){
24 if(IsPalindrome(s, start, i)){
25 par.push_back(s.substr(start, i-start+1));
26 recursivePar(s, i+1, par);
27 par.pop_back();
28 }
29 }
30
31
32 }
33 vector<vector<string>> partition(string s) {
34 // Start typing your C/C++ solution below
35 // DO NOT write int main() function
36 vector<string> par;
37 par.clear();
38 ans.clear();
39 recursivePar(s, 0, par);
40 return ans;
41 }
42 };