Skip to content

Instantly share code, notes, and snippets.

@SuryaPratapK
Created January 25, 2020 16:52
Show Gist options
  • Save SuryaPratapK/f955d6247ac7c31ab2e391d4bf4ca7fd to your computer and use it in GitHub Desktop.
Save SuryaPratapK/f955d6247ac7c31ab2e391d4bf4ca7fd to your computer and use it in GitHub Desktop.
// 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;
}
@Mrinal557
Copy link

in line 26 "remove all characters of first string" should be there instead of what is there

@sumit2609
Copy link

why is matrix dp taken as dp[m+1][n+1].......not as dp[m][n]

@lavkushprasad8051
Copy link

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

@Anishiv05
Copy link

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