Edit Distance (Levenshtein)
Derive the edit-distance recurrence for insert/delete/replace operations and fill the DP table for pairs of strings of varying length.
The Edit Distance Problem
Edit Distance (Levenshtein distance, LeetCode 72) asks: what is the minimum number of insert, delete, or replace operations needed to transform one string into another? For example, to transform 'horse' into 'ros': replace 'h'→'r' (horse→rorse), delete 'r' (rorse→rose), delete 'e' (rose→ros) — 3 operations. Edit distance is foundational in spell-checkers, DNA alignment, and fuzzy matching.
# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)
# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose (delete r at index 1)
# 3. rose → ros (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')DP State and Recurrence
Define dp[i][j] = minimum edit distance between word1[:i] and word2[:j]. If word1[i-1] == word2[j-1], no operation needed: dp[i][j] = dp[i-1][j-1]. Otherwise, take the minimum of three operations: insert dp[i][j-1] + 1, delete dp[i-1][j] + 1, replace dp[i-1][j-1] + 1. Base cases: dp[i][0] = i (delete all of word1) and dp[0][j] = j (insert all of word2).
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
# Base cases
for i in range(m+1): dp[i][0] = i # delete all of word1
for j in range(n+1): dp[0][j] = j # insert all of word2
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 cost
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]
print(edit_distance('horse', 'ros')) # 3
print(edit_distance('intention', 'execution')) # 5All lessons in this course
- Unique Paths and Minimum Path Sum on Grids
- Longest Common Subsequence
- Edit Distance (Levenshtein)
- Space Optimisation for 2D DP