Back

Edit Distance

hard

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

Test Cases

Copy an input into the main harness and Run to verify
Input
word1 = "horse", word2 = "ros"
Expected Output
3

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

Input
word1 = "intention", word2 = "execution"
Expected Output
5

Constraints

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

Hints

Hint 1 — click to reveal

dp[i][j] = min edits to convert word1[0..i) to word2[0..j).

Hint 2 — click to reveal

Match: diagonal. Insert/delete/replace: neighbors + 1.

Java Compiler

Powered by OneCompiler. Starter code loads automatically — edit and hit Run.