Where it runs
1. The problem
You have two words. You want to turn the first into the second with the fewest edits of one character each. There are three kinds of edit: insert one character, delete one character, or replace one character with another. Each edit costs 1.
Turn "horse" into "ros". One cheap way: replace h with r, delete o, delete e. That is 3 edits, and you can't do it in fewer. So the answer is 3.
This number is called the edit distance, or the Levenshtein distance. It shows how far apart two strings are. Spell-checkers are built on it. If you type "recive", the fix "receive" is 1 edit away (insert one e), so it beats words such as "believe", which is 3 edits away.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- longest increasing subsequence
- longest common subsequence between two strings
- minimum edits to turn one string into another
- keep relative order, may skip items
- diff or alignment between two sequences
Looks similar, isn't
- Dynamic programming (1-D)
One index is enough there. Comparing two sequences needs two of them.
- DP on strings (word break)
That page splits a single string into pieces. This one lines two sequences up.
- Binary search (array)
The n log n form of increasing subsequence uses binary search. The table form is the slower one.
- Two pointers (same direction)
Checking whether one string is a subsequence needs no table. Finding the longest common one does.
One sequence of n items costs O(n²) time. Two sequences of n and m cost O(nm), and one kept row is enough.
On LeetCode
Problems that compare two strings cell by cell with a cost or a count per step, such as edits, matching with wildcards or counting ways to form one string from another. The table holds the answer for every pair of prefixes, and the empty prefixes fill the first row and column.
The lesson task. Insert, delete and replace are the left, top and diagonal cells, plus one.
Cell i, j says whether the first i letters of s1 and the first j of s2 make the first i + j letters of s3, and it comes from the cell above or the cell to the left.
The cells hold counts. When the letters match, add the diagonal to the cell above, and an empty target gives 1 down the first column.
With the text on rows and the pattern on columns, a star cell takes the cell above (the star eats one more letter) or the cell to the left (it matches nothing). The base row stays true only while the pattern is all stars.