Edit Distance

Medium#72two strings

You get two words. In one edit you may insert a letter, delete a letter or replace one letter with another. Find the fewest edits that turn the first word into the second. Our example: "pans" → "span" takes 2: insert s in front, delete s at the end.

72 Edit DistanceWalkthrough · 1×

Example: a = "pans", b = "span": the same letters, shifted by one place. Watch the last cell choose a delete over a replace.

spanpans
filledthis step, letters comparedcomes from hereanswer and its path

dp[i][j]: the fewest edits that turn the first i letters of pans into the first j letters of span

01/40
restart · back · play · step
Speed
1function minEdits(a, b):
2 dp = table of len(a) + 1 by len(b) + 1
3 for i from 0 to len(a): dp[i][0] = i // delete all
4 for j from 0 to len(b): dp[0][j] = j // insert all
5 for i from 1 to len(a):
6 for j from 1 to len(b):
7 if a[i - 1] == b[j - 1]:
8 dp[i][j] = dp[i - 1][j - 1]
9 else:
10 dp[i][j] = 1 + min(dp[i - 1][j - 1],
11 dp[i - 1][j],
12 dp[i][j - 1])
13 return dp[len(a)][len(b)]
state
dp
[[–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –], [–, –, –, –, –]]
i
–
j
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Look at the last letters of the two prefixes. If they are equal, keeping them costs nothing, so the cell copies the diagonal.
  2. If they differ, the last edit is one of three: replace a’s letter with b’s (diagonal), delete a’s letter (above) or insert b’s letter (left). The cell is one more than the cheapest of them.
  3. The edges are exact: an empty prefix needs as many edits as the other prefix has letters. Every other cell is built from cells already filled, so the bottom-right cell is the true minimum.

Complexity

Time O(n × m) for words of lengths n and m: one cell per pair of prefixes, each from three neighbours. Memory O(n × m) for the table; the row above and the current row are enough, O(m).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.