Skip to content

149 — Edit Distance

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

149 — Edit Distance

LeetCode 72 · Medium. 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, or replace a character.

🍽️ Intuition

Picture two editors, one holding word1 and one holding word2, comparing them character by character from the start. At position (i, j) — having already reconciled the first i characters of word1 with the first j characters of word2 — if the next characters already match, there's nothing to do; move on. If they don't, there are exactly three edits available: insert the needed character (advance word2's pointer only), delete the extra character (advance word1's pointer only), or replace it (advance both). Each of those three options reduces to the exact same problem one step smaller, which is why this is the archetypal 2-D DP problem — a table over two string indices where every cell looks at three neighbors instead of Longest Common Subsequence's two.

🚩 Pattern-Recognition Cue

"Minimum insert/delete/replace operations to turn one string into another" is the canonical edit-distance tell: the state is (how far into word1, how far into word2), and a mismatch costs 1 + the minimum of three neighboring cells (up = delete, left = insert, diagonal = replace) rather than the two neighbors most other 2-D DP string problems use.

🐢 Brute Force

Recurse over (i, j), the positions reached in word1 and word2, trying all three edits whenever the current characters differ, with no memoization.

func minDistanceBruteForce(_ word1: String, _ word2: String) -> Int {
    let a = Array(word1), b = Array(word2)

    func edit(_ i: Int, _ j: Int) -> Int {
        if i == a.count { return b.count - j }   // insert the rest of word2
        if j == b.count { return a.count - i }   // delete the rest of word1

        if a[i] == b[j] {
            return edit(i + 1, j + 1)
        }

        let insert = 1 + edit(i, j + 1)
        let delete = 1 + edit(i + 1, j)
        let replace = 1 + edit(i + 1, j + 1)
        return min(insert, min(delete, replace))
    }

    return edit(0, 0)
}

// smoke test
print(minDistanceBruteForce("horse", "ros"))   // 3
print(minDistanceBruteForce("intention", "execution"))   // 5
print(minDistanceBruteForce("", "abc"))         // 3

Big-O: O(3^max(m,n)) time in the worst case — every mismatch branches three ways, and the same (i, j) pairs are re-explored down many different edit sequences. O(max(m, n)) space for the recursion stack.

🚀 Optimal

Fill an (m+1) x (n+1) table where dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2 — the first row and column are the cost of inserting/deleting every remaining character, and every other cell either inherits the diagonal (match) or takes 1 + the cheapest of three neighbors (mismatch).

func minDistance(_ word1: String, _ word2: String) -> Int {
    let a = Array(word1), b = Array(word2)
    let m = a.count, n = b.count

    var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
    for i in 0...m { dp[i][0] = i }   // delete all i characters of word1
    for j in 0...n { dp[0][j] = j }   // insert all j characters of word2

    guard m > 0 && n > 0 else { return dp[m][n] }

    for i in 1...m {
        for j in 1...n {
            if a[i - 1] == b[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                let replace = dp[i - 1][j - 1]
                let delete = dp[i - 1][j]
                let insert = dp[i][j - 1]
                dp[i][j] = 1 + min(replace, min(delete, insert))
            }
        }
    }
    return dp[m][n]
}

// smoke test — same cases as the brute force
print(minDistance("horse", "ros"))   // 3
print(minDistance("intention", "execution"))   // 5
print(minDistance("", "abc"))         // 3

Big-O: O(m · n) time — every cell is filled exactly once from at most three already-known neighbors. O(m · n) space for the dp table (collapsible to O(n) with a two-row rolling buffer).

🔑 The Key Insight

Both versions consider the same three edits at every mismatched (i, j) — insert, delete, replace — but the brute force treats every (i, j) as fresh no matter how many edit sequences arrive at it, so the same prefix-pairs are re-solved exponentially many times. The optimal version fills the table row by row, so dp[i-1][j-1], dp[i-1][j], and dp[i][j-1] are always finished answers by the time dp[i][j] needs them. Reusing three already-solved neighbors instead of re-branching three ways from scratch is what turns exponential edit sequences into a flat O(m · n) table fill.

🔗 Related Chapters

  • 2D Dynamic Programming — chapter 27's own "Check Your Understanding" question points here directly: this is the LCS grid shape, but a mismatch pulls the minimum of three neighbors instead of the max of two.
  • Arrays and Strings — both words are converted to [Character] arrays for O(1) indexed access, and dp is a plain 2-D array.

🧸 Memory Sentence

Edit Distance is the three-neighbor grid: a match inherits the diagonal for free, and a mismatch costs one plus the cheapest of delete (up), insert (left), or replace (diagonal).

✅ Check Your Understanding

  1. Why is dp[i][0] = i and dp[0][j] = j, rather than both being 0 the way Longest Common Subsequence initializes its borders?
  2. Which neighboring cell corresponds to "delete," which to "insert," and which to "replace"? Explain each in terms of which of word1's or word2's pointer advances.
  3. Trace minDistance("horse", "ros") far enough to find one full sequence of 3 edits (in terms of insert/delete/replace on individual characters) that transforms "horse" into "ros".

⬅️ Previous: Distinct Subsequences · Next: Burst Balloons ➡️

Clone this wiki locally