150NeetCode 150

119.Edit Distance

Medium2-D Dynamic Programming · 9/11
LeetCode #72Video

Problem

Given two strings word1 and word2, return the minimum number of operations needed to convert word1 into word2.

Allowed operations on word1, each costing 1:

  • Insert a character
  • Delete a character
  • Replace a character

This is the Levenshtein distance between the two strings.

Examples

Input:  word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse → rorse (replace 'h' with 'r')
             rorse → rose  (delete 'r')
             rose  → ros   (delete 'e')
Input:  word1 = "intention", word2 = "execution"
Output: 5
Explanation: intention → inention (delete 't') → enention (replace 'i'→'e')
             → exention (replace 'n'→'x') → exection (replace 'n'→'c')
             → execution (insert 'u')
Input:  word1 = "", word2 = "abc"
Output: 3
Explanation: Insert all three characters.

Constraints

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

💡 Key Insight

Compare the last (or first) characters of the two prefixes. If they are equal, no operation is needed for them: dp[i][j] = dp[i-1][j-1]. Otherwise, one operation fixes the last position, and each operation maps to a smaller subproblem:

  • replace word1[i-1] with word2[j-1] → dp[i-1][j-1]
  • delete word1[i-1] → dp[i-1][j]
  • insert word2[j-1] at the end of word1 → dp[i][j-1]

So dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). Base cases: turning a prefix of length i into "" costs i deletions, and "" into length j costs j inserts.

Recursion (Brute Force)

TimeO(3^(m+n))SpaceO(m + n)

Intuition

solve(i, j) = minimum edits to turn word1[i..] into word2[j..]. If one suffix is empty, the cost is the length of the other. If the front characters match, move both. Otherwise try all three operations.

Algorithm

  1. solve(i, j):
    • If i == m, return n - j (insert the rest).
    • If j == n, return m - i (delete the rest).
    • If word1[i] == word2[j], return solve(i + 1, j + 1).
    • Return 1 + min(solve(i + 1, j + 1) /*replace*/, solve(i + 1, j) /*delete*/, solve(i, j + 1) /*insert*/).
  2. Return solve(0, 0).

Visualization

flowchart TD
    A["solve(0,0)<br/>'ab' → 'b'<br/>a != b"] -->|"replace"| B["solve(1,1)<br/>'b' → '' = 1"]
    A -->|"delete a"| C["solve(1,0)<br/>'b' → 'b' match"]
    A -->|"insert b"| D["solve(0,1)<br/>'ab' → '' = 2"]
    C --> E["solve(2,1) = 0"]
    B --> F["1 + 1 = 2"]
    E --> G["1 + 0 = 1 (best)"]
    D --> H["1 + 2 = 3"]

Code

java
class Solution {
    public int minDistance(String word1, String word2) {
        return solve(word1, word2, 0, 0);
    }

    private int solve(String a, String b, int i, int j) {
        if (i == a.length()) {
            return b.length() - j; // insert remaining chars of b
        }
        if (j == b.length()) {
            return a.length() - i; // delete remaining chars of a
        }
        if (a.charAt(i) == b.charAt(j)) {
            return solve(a, b, i + 1, j + 1); // free match
        }
        int replace = solve(a, b, i + 1, j + 1);
        int delete = solve(a, b, i + 1, j);
        int insert = solve(a, b, i, j + 1);
        return 1 + Math.min(replace, Math.min(delete, insert));
    }
}

Complexity

  • Time: O(3^(m+n)) — up to three branches per step.
  • Space: O(m + n) — recursion depth.

Complexity Comparison

Approach Time Space
Recursion (Brute Force) O(3^(m+n)) O(m + n)
Top-Down Memoization O(m · n) O(m · n)
Bottom-Up 2-D Tabulation O(m · n) O(m · n)
Space-Optimized 1-D DP O(m · n) O(n)

Common Pitfalls

  • Initializing row 0 / column 0 to 0 — they must be j and i (pure inserts / deletes).
  • Adding 1 on a match — equal characters cost nothing.
  • Mixing up which neighbour is insert vs delete; the result is still correct as long as all three neighbours are in the min, but understanding the mapping helps in interviews.
  • In the 1-D version, forgetting to set dp[0] = i at the start of each row or forgetting to save prevDiag before overwriting.
  • Empty strings: if either word is empty the answer is the other's length — make sure your loops handle m = 0 or n = 0.