Code Implementation

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(
                        dp[i - 1][j],    # delete
                        dp[i][j - 1],    # insert
                        dp[i - 1][j - 1] # replace
                    )
        return dp[m][n]
      

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;
        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] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
        return dp[m][n];
    }
};
      

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        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;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 1 + Math.min(
                        dp[i - 1][j - 1],
                        Math.min(dp[i - 1][j], dp[i][j - 1])
                    );
            }
        }
        return dp[m][n];
    }
}
      

var minDistance = function(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = Array.from({length: m + 1}, () => 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;
    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] = 1 + Math.min(
                    dp[i - 1][j],    // delete
                    dp[i][j - 1],    // insert
                    dp[i - 1][j - 1] // replace
                );
            }
        }
    }
    return dp[m][n];
};
      

Problem Description

Given two strings, word1 and word2, your task is to compute the minimum number of operations required to convert word1 into word2. You are allowed to use the following three operations any number of times:

• Insert a character
• Delete a character
• Replace a character

The goal is to find the minimum number of these operations needed. Each operation counts as one step. There is only one valid answer for each input, and you can use the operations in any order or combination as needed.

Thought Process

At first glance, you might think about trying all possible ways to transform word1 into word2 by inserting, deleting, or replacing characters, and counting the number of steps. However, this brute-force approach is not practical because the number of possibilities grows exponentially with the length of the strings.

To optimize, we can observe that the problem has overlapping subproblems: for any given position in the two words, the minimum number of operations needed depends on the solutions to smaller substrings. This is a classic case for dynamic programming. By breaking the problem into smaller subproblems and storing their solutions, we can avoid redundant work. The key is to define a state that represents the minimum operations needed for the first i characters of word1 and the first j characters of word2.

Solution Approach

We use dynamic programming to solve this problem efficiently. Here's the step-by-step approach:

1. Define the DP Table:
   • Let dp[i][j] be the minimum number of operations required to convert the first i characters of word1 to the first j characters of word2.
2. Initialize Base Cases:
   • If i == 0, we need j insertions (turn empty string into word2[0..j-1]).
   • If j == 0, we need i deletions (remove all characters from word1[0..i-1]).
3. Fill the DP Table:
   • For each i from 1 to m (length of word1) and j from 1 to n (length of word2):
   • If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1] (no operation needed).
   • Else, consider the three operations and take the minimum:
     • Insert: dp[i][j-1] + 1
     • Delete: dp[i-1][j] + 1
     • Replace: dp[i-1][j-1] + 1
4. Return the Answer:
   • The answer is dp[m][n], the minimum operations to convert the full word1 to word2.

We use a two-dimensional array because each subproblem depends on both the previous row and column. This guarantees that every subproblem is solved only once, leading to a significant speedup over brute-force recursion.

Example Walkthrough

Let's walk through an example with word1 = "horse" and word2 = "ros".

1. Initialize the DP table:
   • Rows represent characters of "horse" (plus an empty prefix), columns represent "ros" (plus an empty prefix).
   • First row and column are filled with incremental counts (number of insertions or deletions).
2. Compute dp[1][1] to dp[5][3]:
   • Compare 'h' and 'r': not equal, so take min of insert, delete, replace. Result: 1.
   • Compare 'o' and 'r': not equal, repeat process. Result: 2.
   • Compare 'r' and 'r': equal, so copy diagonal value. Result: 1.
   • Continue for all entries, always considering the three possibilities.
3. The final answer is dp[5][3] = 3.
4. The operations could be:
   • horse → rorse (replace 'h' with 'r')
   • rorse → rose (delete 'r')
   • rose → ros (delete 'e')

The DP table ensures we always choose the optimal path at each step.

Time and Space Complexity

Brute-force approach: Would try all possible sequences of operations, leading to exponential time complexity: O(3^{m+n}), where m and n are the lengths of the input strings.

Optimized DP approach:

• Time Complexity: O(mn) — We fill an m+1 by n+1 table, and each cell takes constant time.
• Space Complexity: O(mn) — We store the entire DP table. (This can be reduced to O(n) if we only keep two rows at a time.)

Summary

The Edit Distance problem is a classic example of dynamic programming. By defining a subproblem as the minimum operations needed to convert prefixes of the two words, and building up a solution using a DP table, we achieve an efficient and elegant solution. The key insight is recognizing overlapping subproblems and optimal substructure, allowing us to avoid redundant computation and solve the problem in polynomial time.