Edit Distance

Problem Statement

Given two strings word1 and word2, find the minimum number of operations required to convert word1 into word2. You can perform three operations: Insert a character, Delete a character, or Replace a character.

Example:

• Input: word1 = "horse", word2 = "ros"
• Output: 3 (horse → rorse → rose → ros)

Noob-Friendly Explanation

Imagine you have the word "horse" written on a whiteboard and you want to change it to "ros". You can:

• Insert a letter anywhere
• Delete a letter
• Replace one letter with another

Each action counts as 1 step. You want the fewest steps. It's like autocorrect on your phone — when you misspell a word, it figures out the cheapest way to fix it!

Approach 1: Brute Force (Recursion)

Intuition

Compare characters one by one from the end. If they match, move both pointers. If they don't, try all three operations and pick the one with the minimum cost.

Algorithm

1. If one string is empty, return the length of the other (insert/delete all)
2. If last characters match, solve for the rest (no operation needed)
3. If they don't match, try insert, delete, and replace — return 1 + minimum of all three

public class Solution {
    public int editDistance(String word1, String word2, int m, int n) {
        // If first string is empty, insert all of second
        if (m == 0) return n;
        // If second string is empty, delete all of first
        if (n == 0) return m;

        // If last characters match, no operation needed
        if (word1.charAt(m - 1) == word2.charAt(n - 1)) {
            return editDistance(word1, word2, m - 1, n - 1);
        }

        // Try all three operations and pick minimum
        int insert = editDistance(word1, word2, m, n - 1);
        int delete = editDistance(word1, word2, m - 1, n);
        int replace = editDistance(word1, word2, m - 1, n - 1);

        return 1 + Math.min(insert, Math.min(delete, replace));
    }
}

Complexity Analysis

• Time Complexity: O(3^(m+n)) - Each call can branch into 3 sub-calls
• Space Complexity: O(m + n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Build a 2D table where dp[i][j] represents the edit distance between the first i characters of word1 and the first j characters of word2. Fill it using the same logic as recursion but bottom-up.

Algorithm

1. Create dp[m+1][n+1]. Set dp[i][0] = i and dp[0][j] = j (base cases)
2. For each cell dp[i][j]:
   • If characters match: 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])
3. Answer is dp[m][n]

public class Solution {
    public int editDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        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;

        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],      // delete
                        Math.min(
                            dp[i][j - 1],   // insert
                            dp[i - 1][j - 1] // replace
                        )
                    );
                }
            }
        }

        return dp[m][n];
    }
}

Complexity Analysis

• Time Complexity: O(m * n) - Fill each cell of the m × n table once
• Space Complexity: O(m * n) - The 2D DP table