ExamAdda Logo

Edit Distance

Easy

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

You may perform the following operations:

  1. Insert one character.
  2. Delete one character.
  3. Replace one character with another character.

Example 1

Input

word1 = "horse"
word2 = "ros"

Output

3

Explanation

One way to convert "horse" into "ros" is:

horse → rorse
rorse → rose
rose  → ros

The operations are:

  1. Replace h with r
  2. Delete r
  3. Delete e

Therefore, the minimum number of operations is 3.

Example 2

Input

word1 = "intention"
word2 = "execution"

Output

5

Explanation

One optimal sequence is:

intention → inention
inention  → enention
enention  → exention
exention  → exection
exection  → execution

This requires 5 operations.

Constraints

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

Hints:

Hint 1

Let dp[i][j] represent the minimum operations required to convert the first i characters of word1 into the first j characters of word2.

Hint 2

If the current characters are equal:

word1[i - 1] == word2[j - 1]

 

then no new operation is required:

dp[i][j] = dp[i - 1][j - 1]

Auto
Loading editor...
Input

Expected Output