cheetcode

119. Edit DistanceHard

Find the minimum insertions, deletions, and replacements needed to convert one word into another.

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2.

Valid operations are insert, delete, and replace.

Examples

Input: word1 = "horse", word2 = "ros"
Output: 3

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

Constraints

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