Edit Distance

How it works

We want the minimum number of edits (insert, delete, replace) needed to convert word1 into word2.

The classic DP idea is:

• dp[i][j] = minimum operations to convert word1[i:] into word2[j:]

But to compute dp[i][j], we only need three neighboring states:

• dp[i + 1][j] (delete from word1)
• dp[i][j + 1] (insert into word1)
• dp[i + 1][j + 1] (replace, or match if characters are equal)

That means we don't need the full 2D table. We can compress it into a single 1D array dp, and update it row-by-row (from the end of the strings to the start).

The tricky part of in-place updates is that dp[i + 1][j + 1] (the diagonal value) would get overwritten. So we carry that diagonal value using one extra variable (nextDp), and another temporary variable to shift it correctly while moving left.

We also swap the strings if needed so the DP array is based on the shorter word, keeping memory minimal.

Steps

1. Let m = len(word1) and n = len(word2).
2. If word2 is longer than word1, swap them so n is the smaller length (smaller DP array).
3. Create a 1D array dp of size n + 1:
   • Initialize it for the base case when word1 is exhausted:
     • dp[j] = n - j (we must insert the remaining characters of word2)
4. Iterate i from m - 1 down to 0:
   • Store the old diagonal value using nextDp (this represents dp[i + 1][j + 1] during updates)
   • Update dp[n] = m - i (when word2 is exhausted, we must delete remaining characters of word1)
5. Iterate j from n - 1 down to 0:
   • Save the current dp[j] in temp before overwriting it (this becomes the next diagonal)
   • If word1[i] == word2[j]:
     • no operation needed: set dp[j] = nextDp
   • Otherwise:
     • take 1 + minimum of:
       • delete: dp[j] (still represents dp[i + 1][j])
       • insert: dp[j + 1] (already updated for current row)
       • replace: nextDp (the diagonal dp[i + 1][j + 1])
   • Move the diagonal forward: set nextDp = temp
6. After finishing all updates, dp[0] represents converting the full word1 into the full word2.
7. Return dp[0]

Complexity

• Time complexity: O(m * n)
• Space complexity: O(min(m, n))

Where m is the length of word1 and n is the length of word2.

Things to watch for

Confusing Insert and Delete Operations

When converting word1 to word2, an insert into word1 is equivalent to advancing j (moving forward in word2), while a delete from word1 advances i. Mixing these up leads to incorrect recurrence relations. Remember: insert adds a character to match word2[j], delete removes word1[i].

Incorrect Base Case Initialization

The base cases require returning the number of remaining characters when one string is exhausted. A common mistake is returning 0 or forgetting to handle when i == m (return n - j) or j == n (return m - i). These represent the insertions or deletions needed to complete the transformation.

Forgetting to Add 1 for the Current Operation

When characters don't match, you must add 1 to the minimum of the three recursive calls to account for the current operation. Forgetting this addition results in an answer that's always too small, as it doesn't count the edit being performed at the current position.

Off-by-One Errors in DP Table Dimensions

The DP table needs dimensions (m + 1) x (n + 1) to accommodate the base cases where either string is empty. Using m x n causes index out of bounds errors when accessing dp[m][j] or dp[i][n] for the boundary conditions.

Not Handling Equal Characters Correctly

When word1[i] == word2[j], no operation is needed and you should directly use dp[i+1][j+1] without adding 1. A common mistake is still adding 1 or considering all three operations when characters match, leading to an inflated edit distance.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if m < n:
            m, n = n, m
            word1, word2 = word2, word1

        dp = [n - i for i in range(n + 1)]

        for i in range(m - 1, -1, -1):
            nextDp = dp[n]
            dp[n] = m - i
            for j in range(n - 1, -1, -1):
                temp = dp[j]
                if word1[i] == word2[j]:
                    dp[j] = nextDp
                else:
                    dp[j] = 1 + min(dp[j], dp[j + 1], nextDp)
                nextDp = temp
        return dp[0]

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        if (m < n) {
            swap(m, n);
            swap(word1, word2);
        }

        vector<int> dp(n + 1);
        for (int i = 0; i <= n; i++) dp[i] = n - i;

        for (int i = m - 1; i >= 0; i--) {
            int nextDp = dp[n];
            dp[n] = m - i;
            for (int j = n - 1; j >= 0; j--) {
                int temp = dp[j];
                if (word1[i] == word2[j]) {
                    dp[j] = nextDp;
                } else {
                    dp[j] = 1 + min({dp[j], dp[j + 1], nextDp});
                }
                nextDp = temp;
            }
        }
        return dp[0];
    }
};