Edit Distance

Hard~25 min

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

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

Examples

Example 1
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse → rorse (replace h with r) → rose (remove r) → ros (remove e). Three operations total.
Example 2
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: intention → inention (remove t) → enention (replace i with e) → exention (replace n with x) → exection (replace n with c) → execution (insert u).
Example 3
Input: word1 = "", word2 = ""
Output: 0
Explanation: Both strings are empty, no operations needed.

Constraints

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters
  • Expected time complexity: O(m × n)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run