Dynamic Programming • Strings

Edit Distance

Find the minimum number of operations (Insert, Delete, Replace) required to convert one string into another.

Overview

Also known as the Levenshtein Distance, it's used in spell checkers and DNA sequencing. We build a 2D table where `dp[i][j]` is the edit distance between `word1[0..i]` and `word2[0..j]`.

Base Cases

Converting an empty string to a string of length `j` requires `j` insertions. Converting a string of length `i` to empty requires `i` deletions.

Match vs Mismatch

If `word1[i] == word2[j]`, no new operation is needed. If they differ, we take the minimum cost of the three possible operations plus 1.

The Three Ops

Insert corresponds to moving left (`dp[i][j-1]`). Delete is moving up (`dp[i-1][j]`). Replace is moving diagonally (`dp[i-1][j-1]`).

W1 \ W2	""	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

Code Tracker

:::

1for (let i = 1; i <= m; i++) {

2 for (let j = 1; j <= n; j++) {

3 if (word1[i-1] === word2[j-1]) {

4 dp[i][j] = dp[i-1][j-1];

5 } else {

6 dp[i][j] = 1 + Math.min(

7 dp[i][j-1], // Insert

8 dp[i-1][j], // Delete

9 dp[i-1][j-1] // Replace

10 );

11 }

12 }

13}