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

C++ में एक स्ट्रिंग को दूसरी में बदलने के लिए ऑपरेशन्स प्राप्त करने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास दो स्ट्रिंग्स S और T हैं। हमें ऑपरेशन्स का सबसे छोटा अनुक्रम ढूंढना है जो S को T में बदलता है। यहां ऑपरेशन्स मूल रूप से या तो एक कैरेक्टर को हटाना या डालना है।

उदाहरण के लिए, यदि इनपुट है S = "xxxy", T = "xxyy", तो आउटपुट ["x", "x", "-x", "y", "+y"] होगा, इसका मतलब है पहले दो x रखें, फिर तीसरा x हटाएं, फिर y रखें फिर एक नया y जोड़ें।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम एडिट डिस्टेंस डायनामिक प्रोग्रामिंग का उपयोग करेंगे:

  1. आकार 505×505 का एक टेबल dp बनाएं
  2. एक फंक्शन help() परिभाषित करें जो i, j, S, T लेता है
    • यदि i == S का आकार और j == T का आकार, तो dp[i][j] = 0 वापस करें
    • यदि i == S का आकार, तो dp[i][j] = 1 + help(i, j+1, S, T) वापस करें
    • यदि j == T का आकार, तो dp[i][j] = 1 + help(i+1, j, S, T) वापस करें
    • यदि dp[i][j] != -1, तो dp[i][j] वापस करें
    • dontDo := 1e5, del := 0, insert := 0
    • यदि S[i] == T[j], तो dontDo := help(i+1, j+1, S, T)
    • del := 1 + help(i+1, j, S, T)
    • insert := 1 + help(i, j+1, S, T)
    • minVal := min({dontDo, del, insert})
    • dp[i][j] = minVal वापस करें
  3. एक फंक्शन getPath() परिभाषित करें जो i, j, S, T, curr, ret ऐरे लेता है
    • यदि curr == 0 और i == S का आकार और j == T का आकार, तो वापस करें
    • यदि i < S का आकार और j < T का आकार और S[i] == T[j] और dp[i+1][j+1] == curr:
      • string(1, S[i]) को ret के अंत में डालें
      • getPath(i+1, j+1, S, T, curr, ret)
    • अन्यथा जब dp[i+1][j] + 1 == curr:
      • "-" + string(1, S[i]) को ret के अंत में डालें
      • getPath(i+1, j, S, T, curr-1, ret)
    • अन्यथा:
      • "+" + string(1, T[j]) को ret के अंत में डालें
      • getPath(i, j+1, S, T, curr-1, ret)
  4. मुख्य विधि से:
    • dp को -1 से भरें
    • एक ऐरे ret परिभाषित करें
    • x := help(0, 0, S, T)
    • getPath(0, 0, S, T, x, ret)
    • ret वापस करें

उदाहरण

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

void print_vector(vector<string> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

int dp[505][505];

class Solution {
public:
    int help(int i, int j, string& S, string& T) {
        if (i == S.size() && j == T.size()) return dp[i][j] = 0;
        if (i == S.size()) return dp[i][j] = 1 + help(i, j + 1, S, T);
        if (j == T.size()) return dp[i][j] = 1 + help(i + 1, j, S, T);
        if (dp[i][j] != -1) return dp[i][j];
        int dontDo = 1e5;
        int del = 0;
        int insert = 0;
        if (S[i] == T[j]) dontDo = help(i + 1, j + 1, S, T);
        del = 1 + help(i + 1, j, S, T);
        insert = 1 + help(i, j + 1, S, T);
        int minVal = min({dontDo, del, insert});
        return dp[i][j] = minVal;
    }
    
    void getPath(int i, int j, string& S, string& T, int curr, vector<string>& ret) {
        if (curr == 0 && i == S.size() && j == T.size()) return;
        if (i < S.size() && j < T.size() && S[i] == T[j] && dp[i + 1][j + 1] == curr) {
            ret.push_back(string(1, S[i]));
            getPath(i + 1, j + 1, S, T, curr, ret);
        } else if (dp[i + 1][j] + 1 == curr) {
            ret.push_back("-" + string(1, S[i]));
            getPath(i + 1, j, S, T, curr - 1, ret);
        } else {
            ret.push_back("+" + string(1, T[j]));
            getPath(i, j + 1, S, T, curr - 1, ret);
        }
    }
    
    vector<string> solve(string S, string T) {
        memset(dp, -1, sizeof dp);
        vector<string> ret;
        int x = help(0, 0, S, T);
        getPath(0, 0, S, T, x, ret);
        return ret;
    }
};

vector<string> solve(string source, string target) {
    return (new Solution())->solve(source, target);
}

int main() {
    string S = "xxxy", T = "xxyy";
    print_vector(solve(S, T));
}

इनपुट

"xxxy", "xxyy"

आउटपुट

[x, x, -x, y, +y, ]
  1. - C++ में एक स्ट्रिंग को दूसरी स्ट्रिंग में बदलने के सभी संभावित तरीके प्रिंट करें

    इस समस्या में, हमें दो स्ट्रिंग्स str1 and str2. दी गई हैं। हमारा कार्य एक स्ट्रिंग को दूसरी स्ट्रिंग में बदलने के सभी संभावित तरीके प्रिंट करने के लिए एक प्रोग्राम बनाना है। समस्या विवरण: यहां, हमें उन सभी संभावित तरीकों को खोजने की आवश्यकता है जिनका उपयोग करके हम str1 को str2 में बद

  1. - C++ में स्ट्रिंग को दूसरी स्ट्रिंग में बदलने के लिए कैरेक्टर रिप्लेसमेंट जांचने का प्रोग्राम

    समस्या विवरण मान लीजिए हमारे पास दो लोअरकेस स्ट्रिंग्स s और t हैं। अब एक ऑपरेशन पर विचार करें जहां हम s में एक कैरेक्टर की सभी घटनाओं को दूसरे कैरेक्टर से बदलते हैं। यदि हम इस ऑपरेशन को कितनी भी बार कर सकते हैं, तो हमें जांचना है कि क्या s को t में बदला जा सकता है या नहीं। उदाहरण के लिए, यदि इनपुट ह

  1. C++ में बाइनरी मैट्रिक्स को शून्य मैट्रिक्स में बदलने के लिए ऑपरेशनों की गिनती करने का प्रोग्राम C++ में बाइनरी मैट्रिक्स को शून्य मैट्रिक्स में बदलने के लिए ऑपरेशनों की गिनती करने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। अब एक ऑपरेशन पर विचार करें जहां हम एक सेल लेते हैं और उसे और उसके सभी पड़ोसी सेल्स (ऊपर, नीचे, बाएं, दाएं) को फ्लिप करते हैं। हमें ऑपरेशनों की न्यूनतम संख्या ढूंढनी है जैसे कि मैट्रिक्स में केवल 0 हों। यदि कोई समाधान नहीं है, तो -1 वापस करें। तो, यदि इनप