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 | #include "misc.h"
class Solution{
public:
vector<string> getPalindromes(string s){
int n = s.size();
vector<vector<set<string>>> dp(n, vector<set<string>>(n));
for(int i=0; i<n; ++i){
dp[i][i].insert(s.substr(i, 1));
if(i+1<n && s[i]==s[i+1]){
dp[i][i+1].insert(s.substr(i, 2));
}
}
for(int i=n-1; i>=0; --i){
for(int j=i+2; j<n; ++j){
if(s[i]==s[j]){
dp[i][j].insert(s.substr(i,1)+s.substr(j,1));
for(int i0=i+1; i0<=j-1; ++i0){
for(int j0=i0; j0<=j-1; ++j0){
for(auto p:dp[i0][j0]){
p = s[i] + p + s[j];
cout<<p<<endl;
dp[i][j].insert(p);
}
}
}
}
}
}
set<string> st;
for(int i=0; i<n; ++i){
for(int j=i; j<n; ++j){
st.insert(dp[i][j].begin(), dp[i][j].end());
}
}
return vector<string>{st.begin(), st.end()};
}
};
int main(){
Solution sol;
vector<string> ret = sol.getPalindromes("abacedecba");
for(auto x:ret) cout<<x<<" ";
cout<<endl;
return 0;
}
|
No comments:
Post a Comment