Leetcode 72: Edit Distance

1. Problem Statement (Simple Explanation)

You’re given two strings:

• word1

• word2

You can transform word1 into word2 using three operations:

1. Insert a character

2. Delete a character

3. Replace a character

You must return the minimum number of operations required.

This is the classic Levenshtein distance problem.

2. Examples

Example 1:

Input:

word1 = "horse"

word2 = "ros"

One optimal sequence:

1. "horse" → "rorse" (replace 'h' with 'r')

2. "rorse" → "rose" (delete 'r')

3. "rose" → "ros" (delete 'e')

Output: 3

Example 2:

Input:

word1 = "intention"

word2 = "execution"

One optimal sequence (5 operations):

1. intention → inention (delete 't')

2. inention → enention (replace 'i' with 'e')

3. enention → exention (replace 'n' with 'x')

4. exention → exection (replace 'n' with 'c')

5. exection → execution (insert 'u')

Output: 5

3. Approach – Dynamic Programming (O(m·n))

Let:

• m = len(word1)

• n = len(word2)

Define dp[i][j] as:

• The minimum number of operations required to convert

• word1[0..i-1] into word2[0..j-1]. (So i and j are lengths of prefixes.)

Base Cases:

• Convert empty string to prefix of word2 (i.e., insert all chars):

dp[0][j] = j  (j inserts)

• Convert prefix of word1 to empty string (i.e., delete all chars):

dp[i][0] = i  (i deletes)

Transition:

For i > 0 and j > 0:

1. If last characters match:

if word1[i-1] == word2[j-1]:

    dp[i][j] = dp[i-1][j-1]

2. If last characters differ, we consider three operations:

• Replace last char of word1 with word2[j-1]:

• Cost = dp[i-1][j-1] + 1

• Delete last char from word1:

• Cost = dp[i-1][j] + 1

• Insert last char of word2 into word1:

• Cost = dp[i][j-1] + 1

So:

dp[i][j] = 1 + min(

    dp[i-1][j-1],   // replace

    dp[i-1][j],     // delete

    dp[i][j-1]      // insert

)

Combine both:

if word1[i-1] == word2[j-1]:

    dp[i][j] = dp[i-1][j-1]

else:

    dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

Answer is dp[m][n].

Pseudo-code:

Complexity:

• Time: O(m · n)

• Space: O(m · n) for dp table
  (Can be optimized to O(min(m,n)) with rolling arrays, but full 2D is simplest.)

Constraints are <= 500, so O(m·n) = 250,000 cells is fine.

Java code

C code

C++ code

Python code

JavaScript code