MANG Problem #13: Edit Distance (Hard)

1. 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

Input: word1 = "horse", word2 = "ros"
Output: 3 (horse -> rorse -> rose -> ros)

2. Approach: 2D Bottom-Up DP

graph TD
    Table[DP Table: word1 x word2]
    Match[Match: dp[i-1][j-1]]
    Replace[Replace: dp[i-1][j-1] + 1]
    Delete[Delete: dp[i-1][j] + 1]
    Insert[Insert: dp[i][j-1] + 1]

    Table --> If{word1[i] == word2[j]?}
    If -- Yes --> Match
    If -- No --> Min{Min of...}
    Min --> Replace
    Min --> Delete
    Min --> Insert

We want to find the min distance between every prefix of word1 and word2.

State: dp[i][j] is the edit distance between word1[0...i] and word2[0...j].
Base Case:
- dp[i][0] = i: Converting word of length i to empty string requires i deletions.
- dp[0][j] = j: Converting empty string to word of length j requires j insertions.
Transition:
- If word1[i-1] == word2[j-1]: The characters match! dp[i][j] = dp[i-1][j-1] (No new operation).
- Else: We take the minimum of 3 possibilities + 1:
  - dp[i-1][j] (Delete)
  - dp[i][j-1] (Insert)
  - dp[i-1][j-1] (Replace)

3. Java Implementation

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], // Replace
                           Math.min(dp[i - 1][j],       // Delete
                                    dp[i][j - 1]));      // Insert
            }
        }
    }
    return dp[m][n];
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: Think of the 2D grid as a map. Each cell (i, j) represents the cost to get to that state. Matching characters let you walk diagonally for free.
The Operations:
- Moving Down is a Deletion from word1.
- Moving Right is an Insertion into word1.
- Moving Diagonally (mismatch) is a Replacement.
The Grid: The result is at the bottom-right corner of the matrix, representing the cost to transform the full length of both strings.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(M * N) where M and N are the lengths of the words. We fill every cell in the matrix once."
Interviewer: "How can we optimize space?"
You: "Since we only ever need the previous row (or even just the previous few cells), we can reduce the space complexity from O(M * N) to O(N) by using a single 1D array to store the current row's results."