Leetcode Problem 72 - Edit Distance

 72. Edit Distance

Medium, Dynamic Programming

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.

The Edit Distance problem (also known as the Levenshtein Distance) asks us to compute the minimum number of operations required to convert one string (word1) to another (word2). The allowed operations are:

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

Approach: Dynamic Programming

We can solve this problem using dynamic programming. The idea is to create a 2D table dp, where dp[i][j] represents the minimum number of operations needed to convert the first i characters of word1 to the first j characters of word2.

Transition Formula:

• If word1[i - 1] == word2[j - 1], no operation is needed, and we can take the value from the previous diagonal (dp[i-1][j-1]).
• Otherwise, we need to consider the minimum of three operations:
  1. Insert: Add a character to word1 (dp[i][j-1] + 1).
  2. Delete: Remove a character from word1 (dp[i-1][j] + 1).
  3. Replace: Replace a character from word1 (dp[i-1][j-1] + 1).

Base Cases:

• If one of the strings is empty (i.e., word1[i] == "" or word2[j] == ""), the minimum operations needed is the length of the other string (all insertions or deletions).

Algorithm:

1. Initialize a dp array with dimensions (m + 1) x (n + 1) where m is the length of word1 and n is the length of word2.
2. Iterate through the array, applying the transition formula to fill the table.
3. The value at dp[m][n] will be the answer.

Code:

public class Solution {
    public int MinDistance(string word1, string word2) {
        int m = word1.Length;
        int n = word2.Length;
        
        // Create a 2D dp array where dp[i][j] represents the minimum number of operations
        int[,] dp = new int[m + 1, n + 1];
        
        // Initialize the base cases
        for (int i = 0; i <= m; i++) {
            dp[i, 0] = i;  // Deleting all characters of word1 to match an empty word2
        }
        
        for (int j = 0; j <= n; j++) {
            dp[0, j] = j;  // Inserting all characters of word2 to match an empty word1
        }
        
        // Fill the dp table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i, j] = dp[i - 1, j - 1];  // No operation needed if characters are the same
                } else {
                    dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + 1);
                }
            }
        }
        
        // The result is in the bottom-right corner of the dp table
        return dp[m, n];
    }
}

Explanation of the Code:

1. Initialization:
   • We initialize a 2D array dp where dp[i][j] represents the minimum number of operations to convert the first i characters of word1 to the first j characters of word2.
   • We initialize the first row (dp[0][j]) and first column (dp[i][0]) to represent the cases where one of the words is empty. These represent insertions or deletions.
2. Filling the DP table:
   • For each pair of characters (i, j) in word1 and word2, we check if the characters are the same:
     • If they are the same, no operation is needed, and we take the value from the diagonal (dp[i-1][j-1]).
     • If they are different, we calculate the minimum of the three possible operations (insert, delete, replace).
3. Final Answer:
   • The value at dp[m][n] (where m and n are the lengths of word1 and word2) represents the minimum number of operations needed.

Time and Space Complexity:

• Time Complexity: $O(m \times n)$, where m and n are the lengths of word1 and word2. We fill a 2D DP table of size (m+1) x (n+1), and each cell computation takes constant time.

• Space Complexity: $O(m \times n)$, since we use a 2D array to store the DP table.

---

Example Walkthrough:

Example 1:

Input: word1 = "horse", word2 = "ros"

The DP table starts like this:

    ""  r  o  s
""  0   1  2  3
h   1   1  2  3
o   2   2  1  2
r   3   2  2  2
s   4   3  3  2
e   5   4  4  3

The minimum number of operations to convert "horse" to "ros" is 3, as shown at dp[5][3].

Example 2:

Input: word1 = "intention", word2 = "execution"

The DP table would look like:

       ""   e  x  e  c  u  t  i  o  n
""     0   1  2  3  4  5  6  7  8  9
i      1   1  2  3  4  5  6  7  8  9
n      2   2  2  3  4  5  6  7  8  9
t      3   3  3  3  4  5  6  7  8  9
e      4   4  4  4  4  5  6  7  8  9
n      5   5  5  5  5  5  6  7  8  9
t      6   6  6  6  6  6  6  7  8  9
i      7   7  7  7  7  7  7  7  8  9
o      8   8  8  8  8  8  8  8  8  9
n      9   9  9  9  9  9  9  9  9  9

The minimum number of operations to convert "intention" to "execution" is 5.