Algorithm Day96 - Edit Distance

Posted on In , Views:

🧩 Problem

LeetCode 72 - Edit Distance
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:

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

Example:

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

💡 Idea

This is a classic dynamic programming problem.
We define dp[i][j] as the minimum number of operations required to convert the first i characters of word1 into the first j characters of word2.

DP Transition

If the characters match (word1[i-1] == word2[j-1]): 

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

Otherwise:

1
2
3
4
5
dp[i][j] = 1 + min(
    dp[i-1][j],   // delete
    dp[i][j-1],   // insert
    dp[i-1][j-1]  // replace
)

Base Cases

1
2
dp[0][j] = j  // need j insertions
dp[i][0] = i  // need i deletions

🧠 Complexity

  • Time: O(m × n)
  • Space: O(m × n)

💻 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 1 + Math.min(dp[i - 1][j],
                                   Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
            }
        }
        return dp[m][n];
    }
}

🏁 Summary

This problem demonstrates how dynamic programming elegantly handles string transformations.
We systematically consider all operations (insert, delete, replace) and store intermediate results to build the final answer efficiently.