0

Edit Distance

Hard

Cheapest way to turn one string into another using insert, delete and replace. Each cell picks the cheapest of three neighbours.

two sequencesinsert delete replace
TimeO(n * m)
SpaceO(m)
Inputsource word | target word
-
r
o
s
-
0
1
2
3
h
1
0
0
0
o
2
0
0
0
r
3
0
0
0
s
4
0
0
0
e
5
0
0
0
cell being filledcells it readsreconstructed answer

Turning a prefix into an empty string costs one delete per character, which fills the first row and column.

1 / 17
dp[i][0] = i; dp[0][j] = j
if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(
dp[i-1][j-1], // replace
dp[i][j-1], // insert
dp[i-1][j]) // delete
Why it matters

This is the algorithm behind spell checkers, diff and DNA alignment.

Practise this
Edit DistanceMOne Edit DistanceMDistinct SubsequencesH
Keyboard
space play← → stepr restartctrl K search

More in Dynamic Programming

Kadane (Maximum Subarray)
O(n)
Memoisation vs Brute Force
O(2^n) naive, O(n) memoised
0/1 Knapsack
O(n * W)
Longest Common Subsequence
O(n * m)
Coin Change
O(coins * amount)
Longest Increasing Subsequence
O(n log n)
Minimum Path Sum
O(rows * cols)
Next visualiser
N-Queens