IQ Lab: coding interviews from the first loop

mediumDynamic programming, 2D target 25 min

Edit distance

Not solved yetLeetCode 72. Edit Distance

A spell checker can rank its suggestions by how far each dictionary word is from what you typed. Here distance is counted in edits, and each edit changes one letter in one of three ways:

insert one letter anywhere,
delete one letter,
replace one letter with a different letter.

You get two strings, source and target. Return the smallest number of edits that changes source into target. Every edit costs 1, and a string is 0 edits away from itself.

Example 1

Inputsource = "cat", target = "act"Output2

Delete the c to get "at", then insert a c after the a to get "act". Replacing the first two letters also takes 2.

Example 2

Inputsource = "bread", target = "beard"Output2

Delete the r to get "bead", then insert an r after the a to get "beard". Replacing the three middle letters also works, but costs 3.

Example 3

Inputsource = "rain", target = "shine"Output3

Replace the r with s and the a with h, keep the i and the n, then insert e at the end.

Example 4

Inputsource = "", target = "map"Output3

An empty source needs one insert per letter.

Constraints

0 ≤ len(source), len(target) ≤ 500
Both strings use only lowercase English letters.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern