noodleProblems/
Edit Distance
#79

Edit Distance

AlgorithmmediumStringDynamic Programming

Given two strings word1 and word2, return the minimum number of single-character operations needed to transform word1 into word2.

The permitted operations are: **insert** a character, **delete** a character, and **replace** a character.

Example cases

  • horse to ros
    in word1 = "horse", word2 = "ros"
    out 3
    horse → rorse (replace h), → rose (delete r), → ros (delete e).
  • intention to execution
    in word1 = "intention", word2 = "execution"
    out 5
  • equal
    in word1 = "abc", word2 = "abc"
    out 0

Constraints

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.
Saved
word1 =
"horse"
word2 =
"ros"