The O(n) Club: Edit Distance — When Strings Need Surgery (LeetCode 72)

The O(n) Club: Edit Distance — When Strings Need Surgery (LeetCode 72)

⚡ TL;DR

How do you transform one string into another with as few insertions, deletions, and replacements as possible? You could brute force it, but only if you enjoy stack overflows and unresolved parent issues. With dynamic programming, though, you’re in safe hands — or at least, safer than your last merge conflict.

// Brute-force: For those who hate their CPU
int minDistanceBF(String a, String b, int i, int j) {
    if (i == 0) return j;
    if (j == 0) return i;
    if (a.charAt(i - 1) == b.charAt(j - 1))
        return minDistanceBF(a, b, i - 1, j - 1);
    return 1 + Math.min(
        minDistanceBF(a, b, i - 1, j),      // delete
        Math.min(
            minDistanceBF(a, b, i, j - 1),  // insert
            minDistanceBF(a, b, i - 1, j - 1) // replace
        )
    );
}

🧠 How Devs Usually Mess This Up

Classic slip-ups? Mistake this for the “one edit away” problem, skip all but replacement, and boom! Test cases roast you on a spit. Or maybe you forget to check what happens when one or both strings are empty, so it blows up like a Christmas tree in July. And don’t forget: replacement is one op, not the double whammy of delete-insert you think it is. You’re not being billed by the operation. Chill.

🔍 What’s Actually Going On

Imagine you’re a string surgeon — each letter is a stubborn patient and your goal is minimal trauma. You build a 2D DP table, where dp[i][j] means: “What’s the least pain to turn the first i letters of s1 into the first j letters of s2?” Matching letters? Free pass, like finding a bug you don’t have to fix. Otherwise, you pick your poison: insert, delete, or replace—each costs 1 stitch.

Summary table:

🛠️ PseudoCode

• Create a dp table of size [word1.length+1][word2.length+1].
• Initialize:
  • dp[0][j] = j (thanks, all inserts)
  • dp[i][0] = i (all deletes — we feel you)
• For i from 1 to m:
  • For j from 1 to n:
    If word1.charAt(i-1) == word2.charAt(j-1):
     dp[i][j] = dp[i-1][j-1]
  • Else:
     dp[i][j] = 1 + min( dp[i-1][j], // delete
    dp[i][j-1], // insert
    dp[i-1][j-1] // replace

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero-indexing joy: Remember dp[i][j] maps to word1.charAt(i-1) and word2.charAt(j-1). Don’t go negative or Java will throw shade via exceptions.
• Base case amnesia: If you forget to fill row 0 and col 0, you’ll get mysterious bad results. (Probably in prod, on a Friday.)
• Replacement == one operation: Trying to charge double? HR calls that fraud.
• Space: You can cut memory down to O(min(m, n)) by keeping just two rows if you want to flex.
• Time: O(mn) — unless you love recursion and want your code running until next year.

🧠 Interviewer Brain-Tattoo

“Edit distance: because sometimes, to fix strings or resumes, all you need is one smart table and fewer bad habits.”