मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें s में सबसे लंबे पालिंड्रोमिक उपअनुक्रम की लंबाई ढूंढनी है। हम मान सकते हैं कि s की अधिकतम लंबाई 1000 है। इसलिए यदि इनपुट "bbbab" है, तो आउटपुट 4 होगा। एक संभावित पालिंड्रोमिक उपअनुक्रम "bbbb" है।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
x := s, फिरxको उल्टा करें,n := s का आकार- यदि
n == 0, तो 0 लौटाएं sको अपडेट करें एक खाली स्थान जोड़कर s से पहले, औरxको अपडेट करें एक खाली स्थान जोड़कर x से पहलेret := 0- आकार
(n+1) x (n+1)की एक मैट्रिक्सdpबनाएं i = 1 से nतक:j = 1 से nतक:dp[i][j] := max(dp[i][j-1], dp[i-1][j])- यदि
x[i] == s[j], तोdp[i][j] := max(dp[i][j], 1 + dp[i-1][j-1])
dp[n][n]लौटाएं
उदाहरण
#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];
}
};
int main(){
Solution ob;
cout << (ob.longestPalindromeSubseq("bbbab"));
}
इनपुट
"bbbab"
आउटपुट
4
