Edit Distance

Medium

Given two strings word1 and word2, return the minimum number of operations (insert, delete, or replace a character) to convert word1 into word2.

Example 1

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

Example 2

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

Constraints

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