Medium 2D Table 2-D Dynamic Programming
In plain English: Find the fewest single-character edits (insert, delete, or replace) needed to turn one word into another.
dp[i][j] = edit distance of word1[:i] and word2[:j]. If chars match, no cost (take diagonal). Otherwise, 1 + min(insert, delete, replace) = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]).
Prompt
Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) to convert word1 into word2.
Try to write it from scratch before scrolling down.
Solution
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# base cases: transforming to/from empty string
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # no edit needed
else:
dp[i][j] = 1 + min(
dp[i][j-1], # insert
dp[i-1][j], # delete
dp[i-1][j-1], # replace
)
return dp[m][n]
# Test: min_distance("horse", "ros") == 3
# Test: min_distance("intention", "execution") == 5