मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें इस स्ट्रिंग को पैलिंड्रोम बनाना है। प्रत्येक चरण में हम किसी भी स्थिति पर कोई भी वर्ण सम्मिलित कर सकते हैं, हमें इस पैलिंड्रोम को बनाने के लिए आवश्यक न्यूनतम वर्णों की संख्या ढूंढनी है। यदि स्ट्रिंग "mad" जैसी है, तो उत्तर 2 होगा क्योंकि हम "da" को "mad" से पहले जोड़ सकते हैं, या "am" को "mad" के बाद जोड़कर इसे पैलिंड्रोम बना सकते हैं।
हल करने का दृष्टिकोण
हम LCS (सबसे लंबी सामान्य उपअनुक्रम) दृष्टिकोण का उपयोग करते हैं:
स्ट्रिंग और उसके उल्टे के बीच LCS की लंबाई पैलिंड्रोमिक उपअनुक्रम की लंबाई देती है
न्यूनतम सम्मिलन = स्ट्रिंग की लंबाई - LCS लंबाई
LCS की गणना के लिए 2D DP का उपयोग करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lcs(string s){
string x = s;
int n = s.size();
reverse(x.begin(), x.end());
s = " " + s;
x = " " + x;
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 - 1][j], dp[i][j - 1]);
if(s[i] == x[j]){
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[n][n];
}
int minInsertions(string s) {
return s.size() - lcs(s);
}
};
int main(){
Solution ob;
cout << (ob.minInsertions("mad"));
return 0;
}
इनपुट
"mad"
आउटपुट
2
