All problems

Edit Distance

Medium · dynamic programming

You are given two words, word1 and word2. In one step you may do exactly one of these edits to word1: insert a character anywhere, delete a character, or replace one character with another.

Return the minimum number of steps needed to turn word1 into word2.

Either word may be empty. Turning a word into itself takes 0 steps.

Examples

Example 1

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

Output: 3

horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e).

Example 2

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

Output: 0

The words are already equal, so no edits are needed.

Example 3

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

Output: 3

Starting from nothing, you insert the three letters one by one.

Constraints

• 0 <= len(word1), len(word2) <= 500
• Both words contain only lowercase English letters.