Skip to content

Volume ITechnology

4.24.9 — Edit Distance ​

LeetCode 72 · Hard · ★ Blind 75

The problem ​

Return the minimum number of operations to turn word1 into word2. The allowed operations are insert, delete and replace, each costing 1.

"horse" → "ros"        →  3     (replace h→r, delete r, delete e)
"intention" → "execution"  →  5

Constraints:

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

Plain-English Restatement: You have a starting word and a target word. You can insert a character, delete a character, or swap a character. What is the minimum number of these edits required to morph the starting word into the target word?

Brute Force Approach: At every character mismatch, recursively branch into 3 possibilities: try inserting, trying deleting, and try replacing.

  • Time Complexity: O(3^{\max(m,n)}). At each step, we branch 3 ways.
  • Why it's wasteful: If we delete the first character then insert a character, we might end up with the same remainder of the string as if we just replaced the first character. The brute force tree computes these identical subproblems multiple times.

The pattern ​

Two strings, so a grid. Let dp[i][j] be the edit distance between the first i characters of word1 and the first j of word2.

Look at the last character of each prefix.

If they match, that character costs nothing — align it and move both back:

dp[i][j] = dp[i-1][j-1]

If they differ, you must pay 1 and then do one of three things. All three are available and you take the cheapest:

dp[i][j] = 1 + \min\big(\underbrace{dp[i-1][j-1]}_{\text{replace}},\ \underbrace{dp[i-1][j]}_{\text{delete}},\ \underbrace{dp[i][j-1]}_{\text{insert}}\big)

Reading the three terms is the whole problem, so read them carefully:

  • Replace — change word1[i-1] into word2[j-1]. Both characters are now dealt with, so both indices go back one.
  • Delete — remove word1[i-1]. That character is gone, so i goes back one and j stays; you still owe word2's j characters.
  • Insert — insert word2[j-1] at the end of word1. That satisfies word2's character, so j goes back one and i stays.

The direction of the index that moves is the direction of the operation. If you can say which index moves and why, you will never mix the three up.

The base cases, which are not zero ​

dp[i][0] = i — turning a prefix of length i into the empty string takes i deletions.

dp[0][j] = j — building a prefix of length j from nothing takes j insertions.

This is the first two-string DP in the chapter whose base row and column are not all zeros, and getting them wrong is the usual failure.

The solution ​

python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # (1)

        for i in range(m + 1):
            dp[i][0] = i                      # (2) delete everything
        for j in range(n + 1):
            dp[0][j] = j                      # insert everything

        for i in range(1, m + 1):  # (3)
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:  # (4)
                    dp[i][j] = dp[i - 1][j - 1]           # free
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j - 1],  # (5) replace
                                       dp[i - 1][j],      # delete
                                       dp[i][j - 1])      # insert

        return dp[m][n]
ts
function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));  // (1)

  for (let i = 0; i <= m; i++) dp[i][0] = i;  // (2)
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {  // (3)
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {  // (4)
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);  // (5)
      }
    }
  }

  return dp[m][n];
}

Line by line ​

Here dp[i][j] means "the fewest edits to turn the first i letters of word1 into the first j letters of word2".

(1) A table with one extra row and one extra column. Row 0 and column 0 stand for the empty prefix, with no letters at all. That gives the base cases a place to live.

(2) The first column and first row.

  • dp[i][0] = i: turning i letters into nothing takes i deletions.
  • dp[0][j] = j: turning nothing into j letters takes j insertions.

These are the "base cases that are not zero" the section above warned about.

(3) Fill the rest of the table, row by row, left to right. Every cell reads only cells above it, to its left, or diagonally up-left, and those are already filled.

(4) The last letters match. Nothing needs to change for them. The cost is whatever it took to turn the two shorter prefixes into each other, which is the diagonal cell, dp[i-1][j-1].

(5) The last letters differ, so one edit is needed for them. There are exactly three choices for that edit, and we take the cheapest:

  • Replace the last letter of word1 with the last letter of word2. Then both last letters are dealt with, and the rest costs dp[i-1][j-1].
  • Delete the last letter of word1. It is gone, and we still have to turn the first i − 1 letters into all j letters: dp[i-1][j].
  • Insert the last letter of word2 at the end of word1. That letter is now matched, and we still have to turn all i letters into the first j − 1: dp[i][j-1].

Add 1 for the edit itself.

Trace ​

"horse" to "ros":

        ''  r  o  s
   ''    0  1  2  3
    h    1  1  2  3
    o    2  2  1  2
    r    3  2  2  2
    s    4  3  3  2
    e    5  4  4  3

The answer 3 sits in the corner. Follow it backwards: e deleted, s matched, r deleted… and one replacement of h with r near the start — three operations, matching the problem statement.

Space optimisation ​

The recurrence reads only the previous row and the cell to the left, so two rows suffice:

python
prev = list(range(n + 1))
for i in range(1, m + 1):
    curr = [i] + [0] * n
    for j in range(1, n + 1):
        if word1[i-1] == word2[j-1]:
            curr[j] = prev[j-1]
        else:
            curr[j] = 1 + min(prev[j-1], prev[j], curr[j-1])
    prev = curr
return prev[n]

curr[0] = i is the base case for this row and must be set before the inner loop.

O(n) space, and it is the version real implementations use.

Edge cases ​

  • One or both strings are empty: Handled elegantly by the base cases.
  • Strings are identical: The match condition triggers perfectly along the diagonal, leading to a cost of 0.

Complexity ​

O(mn) time, O(mn) or O(n) space.

There is a faster algorithm when the distance is small — Ukkonen's, O(m \times d) for distance d — which only fills a band around the diagonal. Worth naming; not worth writing.

This one is genuinely everywhere ​

Edit distance is called Levenshtein distance, and it is the most widely used algorithm in this chapter:

  • Spell checkers — rank candidate corrections by edit distance from what you typed.
  • diff and git diff — the same grid on lines instead of characters, which is 4.24.2's relative.
  • DNA sequence alignment — Needleman-Wunsch is this algorithm with per-operation costs instead of 1, and it is one of the foundations of computational biology.
  • Fuzzy search — "did you mean" and typo-tolerant matching in search engines.
  • OCR and speech recognition scoring — word error rate is edit distance on word sequences.

Mentioning one of these is a strong finish, because it shows the algorithm is a tool rather than a puzzle.

Where this goes next ​

  • One Edit Distance — is the distance exactly 1? Answerable in O(n) with two pointers and no table, because you can stop after the first mismatch.
  • Delete Operation for Two Strings — deletions only, so the answer is m + n − 2 × LCS.
  • Minimum ASCII Delete Sum — the same grid with character costs instead of 1, which is exactly the Needleman-Wunsch generalisation.

What the interviewer will push on ​

"Explain the three operations in terms of the indices." Which index moves, and why. If you can do this, the recurrence is not memorised.

"What are the base cases?" i deletions and j insertions — not zero.

"Why is a match free?" No operation is needed; just align the two characters.

"Can you use O(n) space?" Two rows, remembering to set the new row's first cell.

"How would you recover the actual edit script?" Keep the full table and walk backwards from the corner, at each step seeing which of the four predecessors produced the value. Reconstruction needs the table, which is the standing cost of the space optimisation.

"Where is this used?" Spell check, diff, DNA alignment.

One thing to volunteer: name it as Levenshtein distance and give one real use. It reframes the problem from an exercise into something you would reach for.

Next: 4.24.10 Burst Balloons — the hardest DP in the set, and one where the obvious state definition is simply wrong.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet