66. Edit Distance

Hard · Dynamic Programming

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. You may perform the following three operations on a string: insert a character, delete a character, or replace a character.

This is also known as the Levenshtein distance—a measure of how many single-character edits are needed to transform one string into another.

Examples

Example 1
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse → rorse (replace 'h' with 'r')
rorse → rose (delete 'r')
rose → ros (delete 'e')
Total: 3 operations
Example 2
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: intention → exention (replace 'i' with 'e')
exention → exection (replace 'n' with 'c')
exection → execution (insert 'u')
Total: 5 operations (one possible sequence)

Constraints