Edit Distance

Share

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, or replace a character.

Example 1
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse → rorse (replace 'h' with 'r') → rose (delete 'r') → ros (delete 'e').
Example 2
Input: word1 = "intention", word2 = "execution"
Output: 5

Solution Approach - 2D DP

We build a 2D DP table where dp[i][j] represents the minimum edit distance to convert the first i characters of word1 to the first j characters of word2.

  • Base cases: dp[i][0] = i (delete all characters) and dp[0][j] = j (insert all characters).
  • If characters match: dp[i][j] = dp[i-1][j-1].
  • If characters differ: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) representing delete, insert, and replace respectively.
  • The answer is dp[m][n] where m and n are the lengths of the two words.
Java
public class EditDistance {

    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 - 1],
                                    Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
}
Complexity Analysis:

Time complexity: O(m * n) where m and n are the lengths of the two words.
Space complexity: O(m * n) for the 2D DP table; can be optimized to O(min(m,n)) using two rows.