StringProblem 14 of 43

EDIT Distance [Very Imp]

Brute Force
Time: O(3^(m+n))
Space: O(m+n)
Optimal
Time: O(m × n)
Space: O(m × n)

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. The allowed operations are:

  1. Insert a character
  2. Delete a character
  3. Replace a character

This is also known as the Levenshtein Distance.

Example:

  • Input: word1 = "horse", word2 = "ros"

  • Output: 3

  • Explanation:

    • horse → rorse (replace 'h' with 'r')
    • rorse → rose (remove 'r')
    • rose → ros (remove 'e')

  • Input: word1 = "intention", word2 = "execution"

  • Output: 5

Approach 1: Brute Force (Recursion)

Intuition

At each step, compare characters from both strings. If they match, move to next characters. If not, try all three operations and take the minimum.

Algorithm

  1. If either string is empty, return length of the other
  2. If characters match, no operation needed, move both pointers
  3. If they don't match, try insert, delete, replace and take minimum
java
public class Solution {
    public int minDistance(String word1, String word2) {
        return editDistance(word1, word2, 0, 0);
    }
    
    private int editDistance(String word1, String word2, int i, int j) {
        // Base cases
        if (i == word1.length()) {
            return word2.length() - j;
        }
        if (j == word2.length()) {
            return word1.length() - i;
        }
        
        // If characters match
        if (word1.charAt(i) == word2.charAt(j)) {
            return editDistance(word1, word2, i + 1, j + 1);
        }
        
        // Try all three operations
        int insertOp = editDistance(word1, word2, i, j + 1);
        int deleteOp = editDistance(word1, word2, i + 1, j);
        int replaceOp = editDistance(word1, word2, i + 1, j + 1);
        
        return 1 + Math.min(insertOp, Math.min(deleteOp, replaceOp));
    }
}

Complexity Analysis

  • Time Complexity: O(3^(m+n)) - Three choices at each step
  • Space Complexity: O(m+n) - Recursion stack

Approach 2: Memoization (Top-Down DP)

Intuition

Many subproblems are computed multiple times. Use a 2D table to store results.

java
import java.util.*;

public class Solution {
    private int[][] memo;
    
    public int minDistance(String word1, String word2) {
        memo = new int[word1.length()][word2.length()];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return editDistance(word1, word2, 0, 0);
    }
    
    private int editDistance(String word1, String word2, int i, int j) {
        if (i == word1.length()) {
            return word2.length() - j;
        }
        if (j == word2.length()) {
            return word1.length() - i;
        }
        
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        
        if (word1.charAt(i) == word2.charAt(j)) {
            memo[i][j] = editDistance(word1, word2, i + 1, j + 1);
        } else {
            int insertOp = editDistance(word1, word2, i, j + 1);
            int deleteOp = editDistance(word1, word2, i + 1, j);
            int replaceOp = editDistance(word1, word2, i + 1, j + 1);
            memo[i][j] = 1 + Math.min(insertOp, Math.min(deleteOp, replaceOp));
        }
        
        return memo[i][j];
    }
}

Complexity Analysis

  • Time Complexity: O(m × n)
  • Space Complexity: O(m × n)

Approach 3: Tabulation (Bottom-Up DP)

Intuition

Build the solution bottom-up. dp[i][j] represents the minimum operations to convert word1[0..i-1] to word2[0..j-1].

Algorithm

  1. dp[i][0] = i (delete all characters)
  2. dp[0][j] = j (insert all characters)
  3. If characters match: dp[i][j] = dp[i-1][j-1]
  4. Otherwise: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
java
public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        // dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]
        int[][] dp = new int[m + 1][n + 1];
        
        // Base cases
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        
        // Fill the table
        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],
                        Math.min(dp[i][j - 1], dp[i - 1][j - 1])
                    );
                }
            }
        }
        
        return dp[m][n];
    }
}

Complexity Analysis

  • Time Complexity: O(m × n)
  • Space Complexity: O(m × n)

Approach 4: Space Optimized DP

Intuition

Since we only need the previous row to compute the current row, we can reduce space to O(n).

java
public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        // Base case: first row
        for (int j = 0; j <= n; j++) {
            prev[j] = j;
        }
        
        for (int i = 1; i <= m; i++) {
            curr[0] = i;
            
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    curr[j] = prev[j - 1];
                } else {
                    curr[j] = 1 + Math.min(prev[j], 
                                  Math.min(curr[j - 1], prev[j - 1]));
                }
            }
            
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev[n];
    }
}

Complexity Analysis

  • Time Complexity: O(m × n)
  • Space Complexity: O(n)

Reconstructing the Operations

Key Takeaways

  1. Edit Distance is a fundamental string similarity measure
  2. The three operations map directly to DP transitions:
    • Delete → dp[i-1][j]
    • Insert → dp[i][j-1]
    • Replace → dp[i-1][j-1]
  3. Bottom-up DP is preferred for its iterative nature
  4. Space can be optimized from O(m×n) to O(min(m,n))
  5. Used in spell checkers, DNA sequence alignment, plagiarism detection
  6. This is one of the most important DP problems to master
Previous
Word Wrap Problem [VERY IMP]
Next
Find next greater number with same set of digits [Very Very IMP]