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

The problem can be solved using dynamic programming. We create a DP table 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 (because we need i deletions to convert a string of length i to an empty string).
   • dp[0][j] = j for all j (because we need j insertions to convert an empty string to a string of length j).

2. Iteration:

   • For each pair (i, j), we consider three possibilities:
     • Replace: If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1] (no operation needed). Otherwise, dp[i][j] = dp[i-1][j-1] + 1 (one replacement needed).
     • Insert: dp[i][j] = min(dp[i][j], dp[i][j-1] + 1) (insert a character in word1).
     • Delete: dp[i][j] = min(dp[i][j], dp[i-1][j] + 1) (delete a character from word1).

3. Result: dp[m][n] (where m and n are the lengths of word1 and word2 respectively) will contain the minimum edit distance.

Explanation

The dynamic programming approach builds up the solution from smaller subproblems. dp[i][j] leverages the solutions to dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. This avoids redundant calculations and ensures an optimal solution. Each cell in the dp table represents the minimum edit distance for a given prefix of both strings.

Code

function minDistance(word1: string, word2: string): number {
    const m = word1.length;
    const n = word2.length;

    // Create a DP table and initialize it
    const dp: number[][] = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    // Iterate through the DP table
    for (let i = 1; i <= m; i++) {
        for (let 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], dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }

    // The result is in the bottom-right corner of the DP table
    return dp[m][n];
}

Complexity

• Time Complexity: O(m * n), where m and n are the lengths of word1 and word2 respectively. This is due to the nested loops iterating through the DP table.
• Space Complexity: O(m * n), as we use a DP table of size (m+1) x (n+1). This could be optimized to O(min(m,n)) using space optimization techniques, but for clarity, this solution uses the more straightforward approach.