C++ में एडिट डिस्टेंस

मान लीजिए हमारे पास दो शब्द word1 और word2 हैं, हमें word1 को word2 में बदलने के लिए आवश्यक न्यूनतम ऑपरेशंस की संख्या ढूंढनी है। ऑपरेशंस तीन प्रकार के हो सकते हैं: एक कैरेक्टर डालना, एक कैरेक्टर हटाना, और एक कैरेक्टर को बदलना। यदि इनपुट स्ट्रिंग्स "evaluate" और "fluctuate" हैं, तो परिणाम 5 होगा।

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

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• n := w1 का आकार, m := w2 का आकार
• आकार n+1 का एक ऐरे dp बनाएं
• i को 0 से n तक लूप चलाएं:
  • dp[i] := आकार m+1 का नया ऐरे
  • j को 0 से m तक लूप चलाएं:
    • dp[i][j] := 0
    • यदि i = 0, तो dp[i][j] = j
    • अन्यथा जब j = 0, तो dp[i][j] := i
• w1 := खाली स्थान + w1, w2 := खाली स्थान + w2
• i को 1 से n तक लूप चलाएं:
  • j को 1 से m तक लूप चलाएं:
    • यदि w1[i] != w2[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]
• dp[n][m] वापस करें

उदाहरण (C++ कोड)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> 
using namespace std; 
class Solution { 
public: 
    int minDistance(string w1, string w2) { 
        int n = w1.size(); 
        int m = w2.size(); 
        int** dp = new int*[n+1]; 
        for(int i = 0; i <= n; i++){ 
            dp[i] = new int[m+1]; 
            for(int j = 0; j <= m; j++){ 
                dp[i][j] = 0; 
                if(i == 0) dp[i][j] = j; 
                else if(j == 0) dp[i][j] = i; 
            } 
        } 
        w1 = " " + w1; 
        w2 = " " + w2; 
        for(int i = 1; i <= n; i++){ 
            for(int j = 1; j <= m; j++){ 
                if(w1[i] != w2[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")); 
}

इनपुट

"fluctuate" "evaluate"

आउटपुट

5