algoadvance

Leetcode 72. Edit Distance

Problem Statement

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:

1. Insert a character
2. Delete a character
3. Replace a character

Clarifying Questions

1. Can the strings contain any type of characters including spaces and special symbols?
2. What is the maximum possible length of the given strings word1 and word2?
3. Should we consider the case sensitivity of the characters? For example, is a different from A?
4. Is there any preference for one type of operation over another or all operations are considered equally costly?

Strategy

This problem can be effectively solved using Dynamic Programming (DP). We will set up a 2D array dp where dp[i][j] represents the edit distance between the first i characters of word1 and the first j characters of word2.

Steps:

1. Initialization: Initialize a matrix dp of size (len(word1) + 1) x (len(word2) + 1).
2. Base Cases:
   • dp[0][j] = j: To convert an empty word1 to the first j characters of word2, we need j insertions.
   • dp[i][0] = i: To convert the first i characters of word1 to an empty word2, we need i deletions.
3. DP Transition:
   • If the characters match (word1[i-1] == word2[j-1]), then dp[i][j] = dp[i-1][j-1].
   • If they don’t match, consider the following:
     • Insert a character (move j-1): dp[i][j-1] + 1
     • Delete a character (move i-1): dp[i-1][j] + 1
     • Replace a character (move both i-1 and j-1): dp[i-1][j-1] + 1
   • Choose the minimum of these three values.

Code

public class EditDistance {
    
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        // Create a DP array
        int[][] dp = new int[m + 1][n + 1];
        
        // Initialize the base cases
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // Min operations to convert to empty word2
        }
        
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // Min operations to convert from empty word1
        }
        
        // Fill the DP array
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // Characters match, inherit the previous value
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // Characters do not match, consider all operations
                    int insert = dp[i][j - 1] + 1;
                    int delete = dp[i - 1][j] + 1;
                    int replace = dp[i - 1][j - 1] + 1;
                    dp[i][j] = Math.min(insert, Math.min(delete, replace));
                }
            }
        }
        
        // The answer is the last cell of the array
        return dp[m][n];
    }
}

Time Complexity

• Time Complexity: O(m * n), where m is the length of word1 and n is the length of word2. This is because we have a nested loop that iterates over each cell in the DP table.
• Space Complexity: O(m * n) for storing the DP table.

If you have further clarifications or need optimizations or different solutions, please let me know!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?