Medium Tabulation Dynamic Programming
In plain English: Find the fewest edits (insert, delete, or replace a character) to turn one word into another.
Build a 2D table where dp[i][j] = edit distance between word1[:i] and word2[:j]. If chars match, no cost; otherwise take min of insert, delete, replace plus 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 edit_distance(w1, w2):
m, n = len(w1), len(w2)
dp = list(range(n + 1)) # base: transforming "" to w2[:j]
for i in range(1, m + 1):
prev, dp[0] = dp[0], i
for j in range(1, n + 1):
temp = dp[j]
if w1[i - 1] == w2[j - 1]:
dp[j] = prev # match: no extra cost
else:
dp[j] = 1 + min(prev, dp[j], dp[j - 1]) # replace, delete, insert
prev = temp
return dp[n]
# Test: edit_distance("horse", "ros") == 3
# Test: edit_distance("intention", "execution") == 5