Three ways to fix a mismatch
A match still costs nothing — a mismatch now picks the cheapest of insert, delete or replace. About 13 minutes.
How many typos apart?
Your phone suggests "ros" when you type "horse". How different are they? Count the fewest single-letter edits that turn one into the other, where an edit is inserting a letter, deleting one, or replacing one.
Look at the last letters again. If they already match, they cost nothing: just compare what's before them. If they don't, the last edit was one of three things, and each leaves a smaller problem you've already solved.
Three edits, three neighbours
In the grid, each of the three edits points to a neighbour. Replacing the last letter looks diagonally up-left. Deleting a letter from the first word looks up. Inserting a letter looks left. Take the cheapest of the three and add 1.
The edges are straightforward: turning a word into nothing takes one delete per letter, and building a word from nothing takes one insert per letter. "horse" to "ros" comes out at 3.
cost = 0 if a[i - 1] == b[j - 1] else 1
Edges: turning i letters into nothing takes i deletions (column 0); turning nothing into j letters takes j insertions (row 0).
The last letters differ. Replacing leaves a problem costing 2, deleting leaves 4, inserting leaves 3. What does this box cost?
- A3
- B5
- C2
Show the answer
3. Pick the cheapest option (replace, 2) and add 1 for this edit: 3.
Edit distance
You get two strings a and b. Return the fewest single-letter changes that turn a into b, where one change is inserting a letter, deleting a letter or replacing a letter.
a = "horse", b = "ros" → 3
0 ≤ a.length, b.length ≤ 1,000 · lowercase English letters