Given two words, find the fewest operations to turn the first into the second. The allowed operations are insert a character, delete a character, and replace a character.
DSA Animator › DSA Revision › Dynamic Programming › Edit Distance
Remember: above is delete, left is insert, diagonal is replace. Matching characters are free. The video solves Edit Distance (LeetCode 72, Hard) with the 2D String DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Edit Distance animation.
Given two words, find the fewest operations to turn the first into the second. The allowed operations are insert a character, delete a character, and replace a character.
For horse and ros, the answer is 3. Replace h with r, delete r, and delete e.
Trying every sequence of edits explodes quickly. The same prefix pairs appear in many sequences.
Let dp of i and j be the edit distance between the first i characters of word one and the first j of word two. Turning a prefix into an empty string takes i deletions, so the first column is 0, 1, 2 and so on, and the first row likewise. If the characters match, no edit is needed, so copy the diagonal. Otherwise take 1 plus the smallest of three neighbours: above means delete, left means insert, and diagonal means replace. The bottom right cell is the answer.
Fill the first row 0 to 3, and the first column 0 to 5. h against r is a mismatch, so it costs 1 plus 0, which is 1, a replace. o matches the o of ros, so that cell copies the diagonal, 1. r and s continue the table, and the costs grow slowly where characters match. The last row, for e, ends at 3. So the edit distance is 3.
In code, create a table of size m plus 1 by n plus 1. Fill the first row with j, and the first column with i. For each cell, copy the diagonal on a match, otherwise take 1 plus the minimum of the three neighbours. Return the bottom right cell, so it's O of m times n.
Remember: above is delete, left is insert, diagonal is replace. Matching characters are free.