-
Notifications
You must be signed in to change notification settings - Fork 0
/
Palindrome Partitioning .cpp
80 lines (76 loc) · 1.48 KB
/
Palindrome Partitioning .cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<string>
#include<vector>
#include <cctype>
#include<algorithm>
#include<math.h>
using namespace std ;
typedef struct ListNode{
int val;
ListNode * next;
} ListNode;
class Solution {
public:
vector<vector<string> > partition(string s) {
int size=s.length();
vector<vector<vector<string> > > res;
vector<vector<string> > bar;
vector<string> cur;
string foo;
int i,j,m;
cur.push_back(s.substr(0,1));
bar.push_back(cur);
res.push_back(bar);
for(i=1;i<size;i++){
bar.clear();
res.push_back(bar);
for(j=0;j<=i;j++){
foo=s.substr(j,i-j+1);
// cout<<foo<<endl;
if(check(foo)){
// cout<<"!"<<foo<<" "<<j<<endl;
if(!j){
cur.clear();
cur.push_back(foo);
res[i].push_back(cur);
}
else{
bar=res[j-1];
for(m=0;m<bar.size();m++){
bar[m].push_back(foo);
res[i].push_back(bar[m]);
}
}
}
}
}
return res[size-1];
}
bool check(string A){
int size=A.length();
for(int i=0;i<size;i++)
if(A[i]!=A[size-i-1])
return 0;
return 1;
}
void print()
{
string A="aabba";
vector<vector<string> > B;
B=partition(A);
int i,j;
for(i=0;i<B.size();i++){
for(j=0;j<B[i].size();j++)
cout<<B[i][j]<<" ";
cout<<endl;
}
}
};
int main()
{
Solution test;
// cout<<test.Low("A man, a plan, a canal: Panama")<<endl;
test.print();
// cout<<atoi("2147483648")<<endl;
system("pause");
}