Back to ChallengesEdit DistanceMedium 30 min

Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You can Insert, Delete, or Replace characters.

Examples

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

Output: 3

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

Constraints

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

Complexity Analysis

Time

O(m * n)

nested grid scan of word lengths.

Space

O(m * n)

state storage matrix size.

Test Cases

#1 Word mismatch

Input: "horse", "ros"

Expected: 3

#2 Multi-character alignment

Input: "intention", "execution"

Expected: 5

#3 Empty first word

Input: "", "abc"

Expected: 3

JavaScript

Output

Click "Run Code" to see output here...