// A Dynamic Programming based C++ program to find minimum
// number operations to convert str1 to str2
#include <bits/stdc++.h>
using namespace std;
// Utility function to find the minimum of three numbers
int min(int x, int y, int z) { return min(min(x, y), z); }
int editDistDP(string str1, string str2, int m, int n)
{
// Create a table to store results of subproblems
int dp[m + 1][n + 1];
// Fill d[][] in bottom up manner
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// If first string is empty, only option is to
// insert all characters of second string
if (i == 0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is to
// remove all characters of second string
else if (j == 0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last char
// and recur for remaining string
// If the last character is different, consider
// all possibilities and find the minimum
else
dp[i][j]
= min(dp[i][j - 1] + 1, // Insert
dp[i - 1][j] + 1, // Remove
str1[i - 1] == str2[j - 1] ? dp[i - 1][j - 1]:dp[i - 1][j - 1]+2); // Replace
cout << dp[i][j] << " ";
}
cout << "\n";
}
return dp[m][n];
}
// Driver code
int main()
{
// your code goes here
string str1 = "closure";
string str2 = "computer";
cout << editDistDP(str1, str2, str1.length(),
str2.length());
return 0;
}
Ly8gQSBEeW5hbWljIFByb2dyYW1taW5nIGJhc2VkIEMrKyBwcm9ncmFtIHRvIGZpbmQgbWluaW11bQovLyBudW1iZXIgb3BlcmF0aW9ucyB0byBjb252ZXJ0IHN0cjEgdG8gc3RyMgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIFV0aWxpdHkgZnVuY3Rpb24gdG8gZmluZCB0aGUgbWluaW11bSBvZiB0aHJlZSBudW1iZXJzCmludCBtaW4oaW50IHgsIGludCB5LCBpbnQgeikgeyByZXR1cm4gbWluKG1pbih4LCB5KSwgeik7IH0KCmludCBlZGl0RGlzdERQKHN0cmluZyBzdHIxLCBzdHJpbmcgc3RyMiwgaW50IG0sIGludCBuKQp7CgkvLyBDcmVhdGUgYSB0YWJsZSB0byBzdG9yZSByZXN1bHRzIG9mIHN1YnByb2JsZW1zCglpbnQgZHBbbSArIDFdW24gKyAxXTsKCgkvLyBGaWxsIGRbXVtdIGluIGJvdHRvbSB1cCBtYW5uZXIKCWZvciAoaW50IGkgPSAwOyBpIDw9IG07IGkrKykgewoJCWZvciAoaW50IGogPSAwOyBqIDw9IG47IGorKykgewoJCQkvLyBJZiBmaXJzdCBzdHJpbmcgaXMgZW1wdHksIG9ubHkgb3B0aW9uIGlzIHRvCgkJCS8vIGluc2VydCBhbGwgY2hhcmFjdGVycyBvZiBzZWNvbmQgc3RyaW5nCgkJCWlmIChpID09IDApCgkJCQlkcFtpXVtqXSA9IGo7IC8vIE1pbi4gb3BlcmF0aW9ucyA9IGoKCgkJCS8vIElmIHNlY29uZCBzdHJpbmcgaXMgZW1wdHksIG9ubHkgb3B0aW9uIGlzIHRvCgkJCS8vIHJlbW92ZSBhbGwgY2hhcmFjdGVycyBvZiBzZWNvbmQgc3RyaW5nCgkJCWVsc2UgaWYgKGogPT0gMCkKCQkJCWRwW2ldW2pdID0gaTsgLy8gTWluLiBvcGVyYXRpb25zID0gaQoKCQkJLy8gSWYgbGFzdCBjaGFyYWN0ZXJzIGFyZSBzYW1lLCBpZ25vcmUgbGFzdCBjaGFyCgkJCS8vIGFuZCByZWN1ciBmb3IgcmVtYWluaW5nIHN0cmluZwoJCQkvLyBJZiB0aGUgbGFzdCBjaGFyYWN0ZXIgaXMgZGlmZmVyZW50LCBjb25zaWRlcgoJCQkvLyBhbGwgcG9zc2liaWxpdGllcyBhbmQgZmluZCB0aGUgbWluaW11bQoJCQllbHNlCgkJCQlkcFtpXVtqXQoJCQkJCT0gbWluKGRwW2ldW2ogLSAxXSArIDEsIC8vIEluc2VydAoJCQkJCQkJZHBbaSAtIDFdW2pdICsgMSwgLy8gUmVtb3ZlCgkJCQkJCQlzdHIxW2kgLSAxXSA9PSBzdHIyW2ogLSAxXSA/IGRwW2kgLSAxXVtqIC0gMV06ZHBbaSAtIDFdW2ogLSAxXSsyKTsgLy8gUmVwbGFjZQoJCQljb3V0IDw8IGRwW2ldW2pdIDw8ICIgIjsKCQl9CgkJY291dCA8PCAiXG4iOwoJfQoKCXJldHVybiBkcFttXVtuXTsKfQoKLy8gRHJpdmVyIGNvZGUKaW50IG1haW4oKQp7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglzdHJpbmcgc3RyMSA9ICJjbG9zdXJlIjsKCXN0cmluZyBzdHIyID0gImNvbXB1dGVyIjsKCgljb3V0IDw8IGVkaXREaXN0RFAoc3RyMSwgc3RyMiwgc3RyMS5sZW5ndGgoKSwKCQkJCQlzdHIyLmxlbmd0aCgpKTsKCglyZXR1cm4gMDsKfQo=