Back to Problems

Edit Distance

Medium
dynamic-programming

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

This problem is also known as Levenshtein Distance and has applications in spell checkers, DNA sequence alignment, and diff utilities.

Recurrence Relation:

  • If word1[i] == word2[j]: dp[i][j] = dp[i-1][j-1] (no operation needed)
  • Else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    • dp[i-1][j] + 1: delete from word1
    • dp[i][j-1] + 1: insert into word1
    • dp[i-1][j-1] + 1: replace in word1

Example 1

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse -> rorse (replace h with r) -> rose (remove r) -> ros (remove e)

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 = "abc"
Output: 3
Explanation: Insert a, b, and c.

Constraints

  • •0 <= word1.length, word2.length <= 500
  • •word1 and word2 consist of lowercase English letters.
Show Hints (4)
Hint 1: dp[i][j] represents the minimum edits to convert word1[0..i-1] to word2[0..j-1].
Hint 2: If characters match, no operation is needed - carry forward the diagonal value.
Hint 3: Otherwise, consider all three operations and take the minimum.
Hint 4: Base cases: converting empty string to a string of length n requires n insertions.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?