Created
January 25, 2020 16:52
-
-
Save SuryaPratapK/f955d6247ac7c31ab2e391d4bf4ca7fd to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 | |
else if (str1[i - 1] == str2[j - 1]) | |
dp[i][j] = dp[i - 1][j - 1]; | |
// If the last character is different, consider all | |
// possibilities and find the minimum | |
else | |
dp[i][j] = 1 + min(dp[i][j - 1], // Insert | |
dp[i - 1][j], // Remove | |
dp[i - 1][j - 1]); // Replace | |
} | |
} | |
return dp[m][n]; | |
} | |
// Driver program | |
int main() | |
{ | |
// your code goes here | |
string str1 = "sunday"; | |
string str2 = "saturday"; | |
cout << editDistDP(str1, str2, str1.length(), str2.length()); | |
return 0; | |
} |
why is matrix dp taken as dp[m+1][n+1].......not as dp[m][n]
why is matrix dp taken as dp[m+1][n+1].......not as dp[m][n]
bcz we should handle the case where either one string is empty or nor ,or basically 0th column and 0th row is our base case
why is matrix dp taken as dp[m+1][n+1].......not as dp[m][n]
because we are accessing values as dp[i-1][j-1] , so we need to make it as 1-based indexing to get value at dp[0][0]
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
in line 26 "remove all characters of first string" should be there instead of what is there