Skip to main content
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...