Problem 33 - Edit Distance

Explore our archive for previous posts.

Problem 32 - Remove Duplicates from Sorted Array

Problem 31 - Sort Characters By Frequency

Question

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

Example 1:

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

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500

• word1 and word2 consist of lowercase English letters.

Approach

The solution involves using dynamic programming that aims to find the minimum number of operations required to transform one string into another. These operations include insertion, deletion, and replacement of individual characters.

We create a 2D table called dp, where dp[i][j] represents the minimum edit distance between the first i characters of one string (let's call it word1) and the first j characters of another string (let's call it word2). We iteratively fill the dp table and for each cell dp[i][j], we consider the following possibilities:

• Match: If word1[i-1] equals word2[j-1], it means the current characters match, and we don't need to perform any additional operations. In this case, dp[i][j] = dp[i-1][j-1].

• Insertion: We can insert a character into word1, making it equivalent to word2 up to position j. In this case, dp[i][j] = dp[i][j-1] + 1.

• Deletion: We can delete a character from word1, effectively making it equivalent to word2 up to position j-1. In this case, dp[i][j] = dp[i-1][j] + 1.

• Replacement: We can replace the character at word1[i-1] with the character at word2[j-1], making them equal. In this case, dp[i][j] = dp[i-1][j-1] + 1.

By filling the dp table in this manner, we ensure that each cell contains the minimum edit distance between the corresponding substrings of word1 and word2. The final result in dp[m][n] gives us the minimum edit distance between the entire strings, considering all possible edit operations.

Solution

Solve it here

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // dp[i][j] represents the minimum edit distance between 
        // the first i characters of word1 and 
        // the first j characters of word2.
        int[][] dp = new int[m + 1][n + 1];

        // Initialize the first row and first column.
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // Fill in the DP matrix.
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If current characters match, no operation is needed.
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // Otherwise, we have three choices:
                    // 1. Insert a character in word1 (dp[i][j-1] + 1)
                    // 2. Delete a character from word1 (dp[i-1][j] + 1)
                    // 3. Replace a character in word1 (dp[i-1][j-1] + 1)
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

        // dp[m][n] represents the minimum edit distance
        // between the entire word1 and word2.
        return dp[m][n];
    }
}

Time and space complexity

Time Complexity: The time complexity of this solution is O(m * n), where m and n are the lengths of word1 and word2 respectively.

Space Complexity: The space complexity is O(m * n) as well, as we use a 2D array of this size to store intermediate results.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Want free mock interviews?

Simply share our newsletter with your friends, colleagues, or anyone you think would love our coding insights.

When your friends use your referral link to subscribe, you’ll receive special benefits.

• Get a free mock coding interview for 10 referrals

• Get a 1:1 coding Q&A session for 15 referrals

• Get a guest post opportunity for 25 referrals