Edit Distance

Dynamic Programming, problem 9 of 9

Edit Distance

Hard

LC #72

two strings2d dplevenshtein

Not attempted yet

Return the minimum number of operations to turn word1 into word2. Each operation is one of:

  • insert a character
  • delete a character
  • replace a character with another

Example 1

Input: word1 = "horse", word2 = "ros"
Output: 3
horse → rorse (replace h)
rorse → rose (delete r)
rose → ros (delete e)

Example 2

Input: word1 = "intention",
       word2 = "execution"
Output: 5

Example 3

Input: word1 = "", word2 = "abc"
Output: 3

Constraints

  • 0 ≤ len(word1), len(word2) ≤ 500
  • lowercase letters only

Python

Loading draft…

Test results

9 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 6 hidden

Run examples, then submit all tests.