English
72. Edit Distance 
Problem Statement:
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:
rs
impl Solution {
fn min_distance(word1: String, word2: String) -> i32 {
let (m, n) = (word1.len(), word2.len());
let (word1, word2) = (word1.as_bytes(), word2.as_bytes());
let mut dp = vec![vec![0; n + 1]; m + 1];
for i in 0..=m {
for j in 0..=n {
if i == 0 {
dp[i][j] = j as i32;
} else if j == 0 {
dp[i][j] = i as i32;
} else if word1[i - 1] == word2[j - 1] {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + dp[i - 1][j - 1].min(dp[i - 1][j].min(dp[i][j - 1]));
}
}
}
dp[m][n]
}
}
cpp
#include <bits/stdc++.h>
using namespace std;
int minDistance(string word1, string word2)
{
int m = word1.length(),
n = word2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i < m + 1; i++)
for (int j = 0; j < n + 1; j++)
{
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (word1[i - 1] == word2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
}
return dp[m][n];
}
// int main()
// {
// cout << getMinConversions("intention", "execution") << endl;
// }
py
def minDistance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[None] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]))
return dp[m][n]
if __name__ == "__main__":
print(minDistance("intention", "execution"))
go
package main
func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
for i := 0; i <= m; i++ {
for j := 0; j <= n; j++ {
if i == 0 {
dp[i][j] = j
} else if j == 0 {
dp[i][j] = i
} else if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
}
}
}
return dp[m][n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
java
public class EditDistance {
/**
* Time Complexity => O(n^2)
*
* @param str1 String
* @param str2 String
* @return the minimum number of operations required to convert {@code str1} to
* {@code str2}
*/
public int minDistance(String word1, String word2) {
int m = word1.length(),
n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < m + 1; i++)
for (int j = 0; j < n + 1; 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 - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
return dp[m][n];
}
public static void main(String[] args) {
EditDistance ob = new EditDistance();
System.out.println(ob.minDistance("intention", "execution"));
}
}
...