30. Edit distance
An edit inserts one character, deletes one character, or replaces one character by another. Write minDistance a b, the smallest number of edits that turn a into b.
For example, horse becomes ros in three edits: replace h by r, delete r, delete e. The hidden tests compare 20-character words, where exploring every sequence of edits runs out of time.
Examples
- Input
minDistance "horse" "ros"Output3 - Input
minDistance "intention" "execution"Output5
Submitting also runs 7 hidden tests.
Running and submitting solutions, the hints and the editorial come with the Academy Pass. The daily problem is open to every account.
Loading editor…
Type
\to in the editor, or click:Run checks your code against the examples and your custom inputs and records nothing. Submit also runs the hidden tests, confirms the axioms your proof uses and records the result. Each uses one compiler check.
ReadyLn 1, Col 1Lean 4
Draft saved in this browser