C++ में सबसे लंबा पैलिंड्रोमिक परिणाम

मान लीजिए कि हमारे पास एक स्ट्रिंग s है, हमें s में सबसे लंबे पैलिंड्रोमिक अनुक्रम की लंबाई ज्ञात करनी है। हम मान सकते हैं कि s की अधिकतम लंबाई 1000 है। इसलिए यदि इनपुट "bbbab" जैसा है, तो आउटपुट 4 होगा। एक संभावित पैलिंड्रोमिक क्रम "bbbb" है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

x :=s, फिर x को उल्टा करें, n :=s का आकार
अगर n 0 है, तो 0 लौटाएं
s से पहले एक रिक्त स्थान जोड़कर अद्यतन करें, और x से पहले एक रिक्त स्थान जोड़कर x को अपडेट करें
रिट:=0
आकार का एक मैट्रिक्स डीपी बनाएं (n + 1) x (n + 1)
मैं के लिए 1 से n की सीमा में
- जे के लिए n से n की श्रेणी में
  - dp[i, j] :=अधिकतम dp[i, j-1], dp[i-1, j]
  - यदि x[i] =s[j], तो dp[i, j] :=अधिकतम dp[i, j] और 1 + dp[i – 1, j – 1]
रिटर्न डीपी[एन, एन]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestPalindromeSubseq(string s) {
      string x = s;
      reverse(x.begin(), x.end());
      int n = s.size();
      if(!n) return 0;
      s = " " + s;
      x = " " + x;
      int ret = 0;
      vector < vector <int> > dp(n + 1, vector <int>(n + 1));
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= n ; j++){
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            if(x[i] == s[j]) {
               dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
            }
         }
      }
      return dp[n][n];
   }
};
main(){
   Solution ob;
   cout << (ob.longestPalindromeSubseq("bbbab"));
}

इनपुट

"bbbab"