72. Edit Distance

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming — two strings
Difficulty: Hard
Companies: Amazon, Google, Meta, Microsoft, Uber
Frequency: Very High
LeetCode: 72

Problem (one-liner)

Given two words, return the minimum number of operations to convert source into target using insert, delete, or replace a single character.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Minimum operations to transform string A → B
Classic Levenshtein distance
Small local choices with global optimum → optimal substructure

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

BFS on state (string + position) — too many states.
DP cost[row][col] = min ops for source[0:row) → target[0:col) — O(mn) time, O(min(m,n)) space with two rows — optimal.

Optimal Solution

Go

func minDistance(source string, target string) int {
	sourceLen := len(source)
	targetLen := len(target)
	previous := make([]int, targetLen+1)
	current := make([]int, targetLen+1)
	for col := 0; col <= targetLen; col++ {
		previous[col] = col
	}
	for row := 1; row <= sourceLen; row++ {
		current[0] = row
		for col := 1; col <= targetLen; col++ {
			if source[row-1] == target[col-1] {
				current[col] = previous[col-1]
				continue
			}
			deleteCost := previous[col] + 1
			insertCost := current[col-1] + 1
			replaceCost := previous[col-1] + 1
			current[col] = deleteCost
			if insertCost < current[col] {
				current[col] = insertCost
			}
			if replaceCost < current[col] {
				current[col] = replaceCost
			}
		}
		previous, current = current, previous
	}
	return previous[targetLen]
}

JavaScript

function minDistance(source, target) {
  const sourceLen = source.length;
  const targetLen = target.length;
  const previous = new Array(targetLen + 1);
  const current = new Array(targetLen + 1);
  for (let col = 0; col <= targetLen; col += 1) {
    previous[col] = col;
  }
  for (let row = 1; row <= sourceLen; row += 1) {
    current[0] = row;
    for (let col = 1; col <= targetLen; col += 1) {
      if (source[row - 1] === target[col - 1]) {
        current[col] = previous[col - 1];
      } else {
        const deleteCost = previous[col] + 1;
        const insertCost = current[col - 1] + 1;
        const replaceCost = previous[col - 1] + 1;
        current[col] = Math.min(deleteCost, insertCost, replaceCost);
      }
    }
    for (let col = 0; col <= targetLen; col += 1) {
      previous[col] = current[col];
    }
  }
  return previous[targetLen];
}

Walkthrough

source = "horse", target = "ros". Table fills row by row; last cell = 3 (replace h→r, delete r, delete s — or equivalent).

Invariant: previous[col] after row row is min ops to transform source[0:row) into target[0:col).

Edge Cases

One string empty — answer is length of the other (all inserts or deletes)
Equal strings — 0
Repeated characters — replace vs delete tradeoffs

Pitfalls

Off-by-one on indices (row-1 for chars vs row for DP prefix length)
Swapping insert/delete costs when roles of strings differ (always define relative to transforming first arg → second)

Variants

Only insert/delete (no replace) — drop replace branch in recurrence
Weighted operations — min-cost alignment with different costs per op type
K constrained edits — DP with extra dimension for edit budget

Mind-Map Tags

#levenshtein #two-string-dp #rolling-array #string-alignment #minimum-ops