Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सबसे छोटा कॉमन सुपरसीक्वेंस (Shortest Common Supersequence)


समस्या विवरण

दो स्ट्रिंग्स str1 और str2 दी गई हैं। सबसे छोटी स्ट्रिंग ढूंढनी है जिसमें दोनों str1 और str2 सबसीक्वेंस (subsequence) के रूप में मौजूद हों।

सबसीक्वेंस: कुछ अक्षर हटाकर (शून्य या अधिक) प्राप्त स्ट्रिंग।

उदाहरण

इनपुट

"acab", "bac"

आउटपुट

"bacab"

व्याख्या: दोनों दी गई स्ट्रिंग्स "bacab" की सबसीक्वेंस हैं।

समाधान दृष्टिकोण (LCS + मर्ज)

  1. सबसे लंबी कॉमन सबसीक्वेंस (LCS) ढूंढें।
  2. दोनों स्ट्रिंग्स को LCS के साथ मर्ज करें: LCS के अक्षर एक बार लें, बाकी अक्षर क्रम में जोड़ें।

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        string lcs = getLCS(str1, str2);
        string res = "";
        int i = 0, j = 0, k = 0;
        
        while (k < lcs.size()) {
            while (i < str1.size() && str1[i] != lcs[k]) res += str1[i++];
            while (j < str2.size() && str2[j] != lcs[k]) res += str2[j++];
            res += lcs[k++];
            i++; j++;
        }
        while (i < str1.size()) res += str1[i++];
        while (j < str2.size()) res += str2[j++];
        return res;
    }
    
    string getLCS(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        vector> dp(n+1, vector(m+1, 0));
        
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (s1[i-1] == s2[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        
        string lcs = "";
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (dp[i][j] == dp[i-1][j]) i--;
            else if (dp[i][j] == dp[i][j-1]) j--;
            else { lcs += s1[i-1]; i--; j--; }
        }
        reverse(lcs.begin(), lcs.end());
        return lcs;
    }
};

int main() {
    Solution ob;
    cout << ob.shortestCommonSupersequence("acab", "bac");
    return 0;
}

आउटपुट

bacab
  1. C++ में जंप गेम V C++ में जंप गेम V

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। एक चरण में हम इंडेक्स i से कूद सकते हैं: i + x जहां: i + x < n और x की सीमा 1 से d है। = 0 और x की सीमा 1 से d है। arr[k] हो। हम सरणी के किसी भी इंडेक्स से कूदना शुरू कर सकते हैं। हमें अधिकतम इंडेक्स की संख्या ज्ञात करनी है ज

  1. - C++ में K डिजिट्स हटाना

    मान लीजिए हमारे पास एक नॉन-नेगेटिव इंटीजर num है जिसे स्ट्रिंग के रूप में दर्शाया गया है, हमें नंबर से k डिजिट्स हटाने हैं ताकि नया नंबर सबसे छोटा संभव हो। उदाहरण के लिए, अगर इनपुट 1432219 है और k = 3, तो रिजल्ट 1219 होगा। इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे: एक स्टैक st डिफाइन करें,

  1. - C++ में चार डिवाइजर्स

    मान लीजिए हमारे पास एक इंटीजर ऐरे nums है, हमें उस ऐरे में उन इंटीजर्स के डिवाइजर्स का योग ढूंढना है जिनके ठीक चार डिवाइजर्स हैं। अगर ऐरे में ऐसा कोई इंटीजर नहीं है, तो 0 लौटाएं। उदाहरण के लिए, अगर इनपुट [21, 4, 7] है, तो आउटपुट 32 होगा, क्योंकि 21 के चार डिवाइजर्स हैं 1, 3, 7, 21, 4 के तीन डिवाइजर