Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Edit Distance

LeetCode #72Hard

Grid DP · dp[i][j] = min edits word1[:i] → word2[:j]

Given two strings word1 and word2, return the minimum number of operations (insert, delete, or replace a character) required to convert word1 into word2.

Asked atGoogleAmazonMicrosoft

2-D tabulation

time O(m·n)space O(m·n)

step 1 / 18

dp · rows = "horse" (+ ∅), cols = "ros" (+ ∅)

2-D tabulation


▸
1dp = (m+1) × (n+1) grid
2dp[i][0] = i (delete all) ; dp[0][j] = j (insert all)
3for i in 1..m: for j in 1..n:
4    if word1[i−1] == word2[j−1]:
5        dp[i][j] = dp[i−1][j−1]
6    else:
7        dp[i][j] = 1 + min(dp[i−1][j−1], dp[i−1][j], dp[i][j−1])
8 
9return dp[m][n]

state

word1"horse"
word2"ros"
statedp[i][j] = edits word1[:i] → word2[:j]

line 1EDIT DISTANCE: the fewest insertions, deletions, or replacements to turn word1 = "horse" into word2 = "ros". Define dp[i][j] = min edits to convert the first i letters of word1 into the first j letters of word2. The grid is (5+1) × (3+1); row 0 and column 0 stand for the empty prefix ∅. The answer lives in the bottom-right.