Edit Distance medium

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:

  • 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')

Steps and Explanation

This problem can be solved efficiently using dynamic programming. We create a 2D array dp where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2.

  1. Initialization:

    • dp[i][0] = i for all i: To transform an i-length string to an empty string, we need i deletions.
    • dp[0][j] = j for all j: To transform an empty string to a j-length string, we need j insertions.
    • dp[0][0] = 0: Empty string to empty string requires no operations.

  2. Iteration: We iterate through the dp array, filling each cell based on the following recursive relation:

    • If word1[i-1] == word2[j-1]: The last characters are the same, so no operation is needed. dp[i][j] = dp[i-1][j-1]
    • If word1[i-1] != word2[j-1]: We need to consider three possibilities:
      • Replace: dp[i][j] = dp[i-1][j-1] + 1
      • Insert: dp[i][j] = dp[i][j-1] + 1
      • Delete: dp[i][j] = dp[i-1][j] + 1 We choose the minimum of these three possibilities.

  3. Result: The final result is dp[m][n], where m is the length of word1 and n is the length of word2.

Code (C#)

public class Solution {
    public int MinDistance(string word1, string word2) {
        int m = word1.Length;
        int n = word2.Length;

        // Create DP array and initialize
        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;
        }

        // Fill DP array
        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];
                } else {
                    dp[i, j] = Math.Min(dp[i - 1, j - 1], Math.Min(dp[i, j - 1], dp[i - 1, j])) + 1;
                }
            }
        }

        return dp[m, n];
    }
}

Complexity

  • Time Complexity: O(m*n), where m and n are the lengths of the input strings. This is due to the nested loops iterating through the DP array.
  • Space Complexity: O(m*n), the space used by the DP array. This could be optimized to O(min(m,n)) using space optimization techniques, but it's not implemented here for clarity.