All Palindrome Subsequence

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; }