Edit Distance

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazonMicrosoftMetaApple

Problem Description

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

Examples

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.

State Transition and Space Optimization

Let dp[i][j] be the minimum operations to convert word1[0..i-1] to word2[0..j-1]. We look at word1[i - 1] and word2[j - 1]:

If word1[i - 1] == word2[j - 1], no operation is needed for this character: dp[i][j] = dp[i - 1][j - 1]
Otherwise, we choose the minimum of three operations:
- Insert: 1 + dp[i][j - 1]
- Delete: 1 + dp[i - 1][j]
- Replace: 1 + dp[i - 1][j - 1]

Thus: dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

Base cases:

dp[i][0] = i (requires i deletions)
dp[0][j] = j (requires j insertions)

We can optimize space to a 1D array dp of size word2.length() + 1 by updating it row-by-row, keeping track of the diagonal value dp[i-1][j-1] in a temporary variable.

Solution: 1D DP Array

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[] dp = new int[m + 1];

        // base case: converting empty word1 to word2 prefix
        for (int j = 0; j <= m; j++) {
            dp[j] = j;
        }

        for (int i = 1; i <= n; i++) {
            int prevDiag = dp[0]; // holds dp[i - 1][j - 1]
            dp[0] = i; // base case: converting word1 prefix to empty word2

            for (int j = 1; j <= m; j++) {
                int temp = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prevDiag;
                } else {
                    dp[j] = 1 + Math.min(dp[j - 1], // insert
                                 Math.min(dp[j],   // delete
                                          prevDiag // replace
                                 ));
                }
                prevDiag = temp;
            }
        }

        return dp[m];
    }
}

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        dp = list(range(m + 1))

        for i in range(1, n + 1):
            prev_diag = dp[0]
            dp[0] = i
            for j in range(1, m + 1):
                temp = dp[j]
                if word1[i - 1] == word2[j - 1]:
                    dp[j] = prev_diag
                else:
                    dp[j] = 1 + min(
                        dp[j - 1],  # insert
                        dp[j],      # delete
                        prev_diag   # replace
                    )
                prev_diag = temp

        return dp[m]

#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
        int n = word1.length(), m = word2.length();
        std::vector<int> dp(m + 1);

        for (int j = 0; j <= m; j++) {
            dp[j] = j;
        }

        for (int i = 1; i <= n; i++) {
            int prevDiag = dp[0];
            dp[0] = i;
            for (int j = 1; j <= m; j++) {
                int temp = dp[j];
                if (word1[i - 1] == word2[j - 1]) {
                    dp[j] = prevDiag;
                } else {
                    dp[j] = 1 + std::min({dp[j - 1], dp[j], prevDiag});
                }
                prevDiag = temp;
            }
        }

        return dp[m];
    }
};

Complexity Analysis:

Time Complexity: O(N * M) where N is the length of word1 and M is the length of word2.
Space Complexity: O(M) to store the 1D DP array.