# 72. Edit Distance
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 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')
# Solution
Approach 1: DP in 2D. Space can be optimized to be O(N) instead of O(MN) where M and N are lengths of the words.
# Code (Python)
Approach 1:
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# table[j][i] -- edit distance between word1[:j] and word2[:i]
table = [[float('inf') for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
table[0][0] = 0
for i in range(1, len(word2) + 1):
table[0][i] = i
for j in range(1, len(word1) + 1):
table[j][0] = j
for i in range(1, len(word2) + 1):
if word1[j-1] == word2[i-1]:
table[j][i] = table[j-1][i-1]
else:
table[j][i] = min(table[j-1][i-1], table[j][i-1], table[j-1][i]) + 1
return table[-1][-1]
def minDistance(self, word1: str, word2: str) -> int:
# space optimization: O(N) instead of O(MN) where M and N are lengths
table = [i for i in range(len(word2) + 1)]
for j in range(1, len(word1) + 1):
table_prev_val = table[0]
table[0] = j
for i in range(1, len(word2) + 1):
if word1[j-1] == word2[i-1]:
table_j_i = table_prev_val
else:
table_j_i = min(table_prev_val, table[i-1], table[i]) + 1
table_prev_val = table[i]
table[i] = table_j_i
return table[-1]
# Code (C++)
Approach 1:
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size();
int n2 = word2.size();
int ops[n1+1][n2+1];
ops[0][0] = 0;
for (int i = 1; i <= n1; ++i)
ops[i][0] = i;
for (int i = 1; i <= n2; ++i)
ops[0][i] = i;
for (int i = 1; i <= n1; ++i)
{
for (int j = 1; j <= n2; ++j)
{
ops[i][j] = std::min(ops[i-1][j] + 1,
std::min(ops[i][j-1] + 1,
ops[i-1][j-1] + ((word1[i-1] == word2[j-1]) ? 0 : 1)));
}
}
return ops[n1][n2];
}
};
// Space can be optimized to be O(N) instead of O(MN) where M and N are lengths of the words.
class Solution {
public:
int minDistance(string word1, string word2) {
int n1 = word1.size();
int n2 = word2.size();
int prev[n2+1];
for (int len2 = 0; len2 <= n2; ++len2)
prev[len2] = len2;
for (int len1 = 1; len1 <= n1; ++len1)
{
int tmp = prev[0];
prev[0] = len1;
for (int len2 = 1; len2 <= n2; ++len2)
{
int curr = std::min(prev[len2-1] + 1,
std::min(prev[len2] + 1,
tmp + ((word1[len1-1] == word2[len2-1]) ? 0 : 1)));
tmp = prev[len2];
prev[len2] = curr;
}
}
return prev[n2];
}
};