C++ में दो स्ट्रिंग्स के बीच न्यूनतम एडिट दूरी खोजें

दो शब्द S और T दिए गए हैं, S को T में बदलने के लिए आवश्यक न्यूनतम ऑपरेशंस (इंसर्शन, डिलीशन, रिप्लेसमेंट) की संख्या ज्ञात करें। इसे लीवेंस्टाइन दूरी भी कहते हैं।

उदाहरण: "evaluate" और "fluctuate" → 5 ऑपरेशंस।

समाधान दृष्टिकोण (डायनामिक प्रोग्रामिंग)

1. आकार (n+1) x (m+1) का DP टेबल बनाएं।
2. आधार मामले: dp[i][0] = i, dp[0][j] = j।
3. दोनों स्ट्रिंग्स के आगे एक स्पेस जोड़ें (1-आधारित इंडेक्सिंग)।
4. i = 1 से n, j = 1 से m तक:
   • यदि s[i] != t[j]: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])।
   • अन्यथा: dp[i][j] = dp[i-1][j-1]।
5. dp[n][m] वापस करें।

C++ कार्यान्वयन

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

class Solution {
public:
    int minDistance(string s, string t) {
        int n = s.size(), m = t.size();
        vector> dp(n + 1, vector(m + 1));
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;
        s = " " + s;
        t = " " + t;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i] != t[j])
                    dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                else
                    dp[i][j] = dp[i-1][j-1];
            }
        }
        return dp[n][m];
    }
};

int main() {
    Solution ob;
    cout << ob.minDistance("fluctuate", "evaluate");
    return 0;
}

इनपुट

"fluctuate" "evaluate"

आउटपुट

5