मान लीजिए हमारे पास दो स्ट्रिंग्स text1 और text2 हैं, हमें उनके सबसे लंबे सामान्य उपअनुक्रम (Longest Common Subsequence - LCS) की लंबाई ज्ञात करनी है। एक उपअनुक्रम वह स्ट्रिंग है जो मूल स्ट्रिंग से कुछ वर्णों को हटाकर (बिना क्रम बदले) बनती है। उदाहरण के लिए, "abe" "abcde" का उपअनुक्रम है लेकिन "adc" नहीं।
यदि इनपुट "abcde" और "ace" है, तो परिणाम 3 होगा (उपअनुक्रम "ace")।
समाधान दृष्टिकोण
हम डायनामिक प्रोग्रामिंग का उपयोग करते हैं:
- n := text1 का आकार, m := text2 का आकार।
- यदि n या m शून्य है, तो 0 वापस करें।
- दोनों स्ट्रिंग्स के आगे एक खाली स्थान जोड़ें (1-आधारित इंडेक्सिंग के लिए)।
- आकार (n+1) x (m+1) का एक 2D DP सरणी बनाएं।
- i = 1 से n तक और j = 1 से m तक पुनरावृति करें:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])- यदि
s[i] == x[j], तोdp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1])
dp[n][m]वापस करें।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestCommonSubsequence(string s, string x) {
int n = s.size();
int m = x.size();
if (!n || !m) return 0;
s = " " + s;
x = " " + x;
vector> dp(n + 1, vector(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if (s[i] == x[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][m];
}
};
int main() {
Solution ob;
cout << ob.longestCommonSubsequence("abcde", "ace");
return 0;
}
इनपुट
"abcde" "ace"
आउटपुट
3