Problem of The Day: Edit Distance
Problem Statement
My Solution [Accepted]
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
COLS = len(word1) + 1
ROWS = len(word2) + 1
dp = [[0 for _ in range(COLS)] for _ in range(ROWS)]
# left -> right: we are trying to delete character
dp[0] = [col for col in range(COLS)]
# top -> bottom: we are trying to insert character
for row in range(ROWS):
dp[row][0] = row
for row in range(1, ROWS):
for col in range(1, COLS):
delete = dp[row - 1][col]
insert = dp[row][col - 1]
replace = dp[row - 1][col - 1]
if word1[col - 1] == word2[row - 1]:
dp[row][col] = min(replace, min(insert, delete) + 1)
else:
dp[row][col] = min(replace, insert, delete) + 1
return dp[-1][-1]
Editorial
Approach 1: Recursion
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# calculate the distance between two words using recursion
return self.minDistanceRecur(word1, word2, len(word1), len(word2))
def minDistanceRecur(
self, word1: str, word2: str, word1Index: int, word2Index: int
) -> int:
# base cases
if (
word1Index == 0
): # if word1 is empty, the minimum distance is the length of word2
return word2Index
if (
word2Index == 0
): # if word2 is empty, the minimum distance is the length of word1
return word1Index
# if the characters are same, continue with next pair of characters
if word1[word1Index - 1] == word2[word2Index - 1]:
return self.minDistanceRecur(
word1, word2, word1Index - 1, word2Index - 1
)
else:
# calculate the cost of insert, delete, and replace operations
insertOperation = self.minDistanceRecur(
word1, word2, word1Index, word2Index - 1
)
deleteOperation = self.minDistanceRecur(
word1, word2, word1Index - 1, word2Index
)
replaceOperation = self.minDistanceRecur(
word1, word2, word1Index - 1, word2Index - 1
)
# return the minimum cost
return min(insertOperation, deleteOperation, replaceOperation) + 1
public class Solution {
public int MinDistance(string word1, string word2) {
return MinDistanceRecur(word1, word2, word1.Length, word2.Length);
}
public int MinDistanceRecur(string word1, string word2, int word1Index,
int word2Index) {
if (word1Index == 0) {
return word2Index;
}
if (word2Index == 0) {
return word1Index;
}
if (word1[word1Index - 1] == word2[word2Index - 1]) {
return MinDistanceRecur(word1, word2, word1Index - 1,
word2Index - 1);
} else {
int insertOperation =
MinDistanceRecur(word1, word2, word1Index, word2Index - 1);
int deleteOperation =
MinDistanceRecur(word1, word2, word1Index - 1, word2Index);
int replaceOperation =
MinDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
return Math.Min(insertOperation,
Math.Min(deleteOperation, replaceOperation)) +
1;
}
}
}
Approach 2: Memoization: Top-Down Dynamic Programming
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
memo = [
[None for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)
]
def minDistanceRecur(word1, word2, word1Index, word2Index):
if word1Index == 0:
return word2Index
if word2Index == 0:
return word1Index
if memo[word1Index][word2Index] is not None:
return memo[word1Index][word2Index]
minEditDistance = 0
if word1[word1Index - 1] == word2[word2Index - 1]:
minEditDistance = minDistanceRecur(
word1, word2, word1Index - 1, word2Index - 1
)
else:
insertOperation = minDistanceRecur(
word1, word2, word1Index, word2Index - 1
)
deleteOperation = minDistanceRecur(
word1, word2, word1Index - 1, word2Index
)
replaceOperation = minDistanceRecur(
word1, word2, word1Index - 1, word2Index - 1
)
minEditDistance = (
min(insertOperation, deleteOperation, replaceOperation) + 1
)
memo[word1Index][word2Index] = minEditDistance
return minEditDistance
return minDistanceRecur(word1, word2, len(word1), len(word2))
public class Solution {
public int MinDistance(string word1, string word2) {
int?[][] memo = new int ?[word1.Length + 1][];
for (int i = 0; i <= word1.Length; i++)
memo[i] = new int?[word2.Length + 1];
return MinDistanceRecur(word1, word2, word1.Length, word2.Length);
int MinDistanceRecur(string word1, string word2, int word1Index,
int word2Index) {
if (word1Index == 0)
return word2Index;
if (word2Index == 0)
return word1Index;
if (memo[word1Index][word2Index] != null)
return memo[word1Index][word2Index].Value;
int minEditDistance = 0;
if (word1[word1Index - 1] == word2[word2Index - 1])
minEditDistance = MinDistanceRecur(word1, word2, word1Index - 1,
word2Index - 1);
else {
int insertOperation =
MinDistanceRecur(word1, word2, word1Index, word2Index - 1);
int deleteOperation =
MinDistanceRecur(word1, word2, word1Index - 1, word2Index);
int replaceOperation = MinDistanceRecur(
word1, word2, word1Index - 1, word2Index - 1);
minEditDistance =
Math.Min(insertOperation,
Math.Min(deleteOperation, replaceOperation)) +
1;
}
memo[word1Index][word2Index] = minEditDistance;
return minEditDistance;
}
}
}
Approach 3: Bottom-Up Dynamic Programming: Tabulation
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
word1Length = len(word1)
word2Length = len(word2)
if word1Length == 0:
return word2Length
if word2Length == 0:
return word1Length
dp = [
[0 for _ in range(word2Length + 1)] for _ in range(word1Length + 1)
]
for word1Index in range(1, word1Length + 1):
dp[word1Index][0] = word1Index
for word2Index in range(1, word2Length + 1):
dp[0][word2Index] = word2Index
for word1Index in range(1, word1Length + 1):
for word2Index in range(1, word2Length + 1):
if word2[word2Index - 1] == word1[word1Index - 1]:
dp[word1Index][word2Index] = dp[word1Index - 1][
word2Index - 1
]
else:
dp[word1Index][word2Index] = (
min(
dp[word1Index - 1][word2Index],
dp[word1Index][word2Index - 1],
dp[word1Index - 1][word2Index - 1],
)
+ 1
)
return dp[word1Length][word2Length]
public class Solution {
public int MinDistance(string word1, string word2) {
int word1Length = word1.Length;
int word2Length = word2.Length;
if (word1Length == 0) {
return word2Length;
}
if (word2Length == 0) {
return word1Length;
}
int[,] dp = new int[word1Length + 1, word2Length + 1];
for (int word1Index = 1; word1Index <= word1Length; word1Index++) {
dp[word1Index, 0] = word1Index;
}
for (int word2Index = 1; word2Index <= word2Length; word2Index++) {
dp[0, word2Index] = word2Index;
}
for (int word1Index = 1; word1Index <= word1Length; word1Index++) {
for (int word2Index = 1; word2Index <= word2Length; word2Index++) {
if (word2[word2Index - 1] == word1[word1Index - 1]) {
dp[word1Index, word2Index] =
dp[word1Index - 1, word2Index - 1];
} else {
dp[word1Index, word2Index] =
Math.Min(dp[word1Index - 1, word2Index],
Math.Min(dp[word1Index, word2Index - 1],
dp[word1Index - 1, word2Index - 1])) +
1;
}
}
}
return dp[word1Length, word2Length];
}
}