In the Leetcode Edit Distance problem solution Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Example 1:
Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
Example 2:
Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)
Constraints:
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.
Solution in C Programming
#include <string.h>
int min(int a, int b, int c){
int m = a;
if(a > b){
m = b;
}
if(m > c){
return c;
}else{
return m;
}
}
int minDistance(char * word1, char * word2){
int l1 = strlen(word1);
int l2 = strlen(word2);
char *w1 = (char *)malloc((l1+3)*sizeof(char));
char *w2 = (char *)malloc((l2+3)*sizeof(char));
for(int i=0;i<=strlen(word1)+1;i++){
if(i==0){
w1[i] = '#';
}else if(i<=strlen(word1)){
w1[i] = word1[i-1];
}else{
w1[i] = '\0';
}
}
for(int i=0;i<=strlen(word2)+1;i++){
if(i==0){
w2[i] = '#';
}else if(i<=strlen(word2)){
w2[i] = word2[i-1];
}else{
w2[i] = '\0';
}
}
// printf("%s\n", w1);
// printf("%s\n", w2);
int m[l2+1][l1+1];
for(int i=0;i<strlen(w2);i++){
m[i][0] = i;
}
for(int j=0;j<strlen(w1);j++){
m[0][j] = j;
}
for(int i=1;i<=l2;i++){
for(int j=1;j<=l1;j++){
m[i][j] = min(m[i-1][j]+1, m[i][j-1]+1, m[i-1][j-1]+(int)(w1[j]!=w2[i]));
}
}
// for(int i=0;i<=l2;i++){
// for(int j=0;j<=l1;j++){
// printf("%d ",m[i][j]);
// }
// printf("\n");
// }
return m[l2][l1];
}Solution in C++ Programming
class Solution
{
public:
int minDistance(string word1, string word2)
{
int n = word1.size();
int m = word2.size();
int dp[n+1][m+1];
// Initialize inserting i times option
for (int i = 0; i<=m; i++)
dp[0][i]=i;
// Initialize removing i times option
for (int i = 0; i<=n; i++)
dp[i][0]=i;
for (int i = 1; i<=n; i++)
{
for (int j = 1; j<=m; j++)
{
// chusing the lowest count to get to i,j
// keeping if characters are the same
int count = dp[i-1][j-1];
// if not the same replacing option path => count increase
if (word1[i-1] != word2[j-1])
count++;
// compare to getting to i,j by removing option path
count = min(dp[i-1][j]+1,count);
// compare to getting to i,j by inserting option path
count = min(dp[i][j-1]+1,count);
dp[i][j] = count;
}
}
return dp[n][m];
}
};Solution in Java Programming
class Solution {
public int minDistance(String word1, String word2) {
int length1 = word1.length();
int length2 = word2.length();
int [][] dp = new int[length1+1][length2+1];
for (int i=0; i<=length1; i++) {
for (int j=0; j<=length2; j++) {
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (word1.charAt(i-1) == word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else {
dp[i][j] = 1 + Math.min(dp[i][j-1],
Math.min(dp[i-1][j],
dp[i-1][j-1]));
}
}
}
return dp[length1][length2];
}
}Solution in Python Programming
class Solution:
def minDistance(self, word1, word2):
memo = {}
def edit(word1, word2):
if (word1, word2) in memo:
return memo[word1, word2]
if len(word1) == 0 or len(word2) == 0:
return len(word1) + len(word2)
if word1[0] == word2[0]:
memo[word1, word2] = edit(word1[1:], word2[1:])
return memo[word1, word2]
memo[word1, word2] = min(1 + edit(word1[1:], word2),
1 + edit(word1, word2[1:]),
1 + edit(word1[1:], word2[1:]))
return memo[word1, word2]
return edit(word1, word2)Solution in C# Programming
public class Solution {
public int calculate(string w1, string w2, int m, int n, int[,] dp)
{
//if m string ended before that means m has to be added with 1 to be equal to n
if(m == -1)
return n+1;
if(n == -1)
return m+1;
//return stored value
if(dp[m,n] != -1)
return dp[m,n];
//if equal then move back and continue calculation, no operations required
if(w1[m] == w2[n])
return dp[m,n] = calculate(w1,w2,m-1,n-1,dp);
//replaced one and both are now same, so move both back
int a = calculate(w1,w2,m-1,n-1,dp); //replace
//insert elem in m,so move n back
int b = calculate(w1,w2,m,n-1,dp); // insert
//delete m elem so move m back but n as it is
int c = calculate(w1,w2,m-1,n,dp); // delete
//Take min of above operations + 1 (recent operation)
return dp[m,n] = 1 + Math.Min(a,Math.Min(b,c));
}
public int MinDistance(string word1, string word2) {
int m = word1.Length;
int n = word2.Length;
int[,] dp = new int[m,n];
//Initialization
for(int i=0; i< m; i++)
{
for(int j=0; j<n; j++)
{
dp[i,j] = -1;
}
}
int ans = calculate(word1,word2,m-1,n-1,dp);
return ans;
}
}Also read,