Medium#728 min readDynamic Programming2D DPStringsLeetCode

Edit Distance

Match-or-edit 2D DP with 1D row collapse

dp[i][j] = min edits for s1[0..i] → s2[0..j]. Three transitions: insert, delete, replace.

Published Apr 17, 2026

Problem

Given two strings word1 and word2, return the minimum number of single-character operations to transform word1 into word2. Operations: insert, delete, or replace a character.

Input

Output

Explanation

horse → rorse (replace h→r) → rose (remove r) → ros (remove e).

Input

Output

Input

Output

Explanation

Insert three characters.

Intuition

Consider the last characters. Two cases:

They match — no edit at this position. The problem reduces to word1[..i-1] → word2[..j-1]: dp[i][j] = dp[i-1][j-1].
They differ — we must pay one edit. The question is which edit:
- Insert word2[j-1] on the right of word1[..i] → reduces to word1[..i] → word2[..j-1]: 1 + dp[i][j-1].
- Delete word1[i-1] → reduces to word1[..i-1] → word2[..j]: 1 + dp[i-1][j].
- Replace word1[i-1] with word2[j-1] → reduces to word1[..i-1] → word2[..j-1]: 1 + dp[i-1][j-1].

Take the min across all three.

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

Base cases: dp[0][j] = j (insert all of word2's first j chars), dp[i][0] = i (delete all of word1's first i chars).

Edit Distance is #1143 LCS's twin: match branch, skip branch, aggregate across three neighbors. The only differences: the aggregator is min (not max), and mismatches cost +1 instead of skipping freely. Once you recognize the shape, the 1D rolling form is mechanical — same prev_diag cache trick, same shorter-axis-inner iteration.

Approach

2D Table

TimeO(m · n)

SpaceO(m · n)

Literal translation. Transparent and easy to debug — print the table after each row to see edits propagate from the boundaries inward.

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let a = word1.as_bytes();
        let b = word2.as_bytes();
        let m = a.len();
        let n = b.len();
        let mut dp = vec![vec![0i32; n + 1]; m + 1];
        for i in 0..=m {
            dp[i][0] = i as i32;
        }
        for j in 0..=n {
            dp[0][j] = j as i32;
        }
        for i in 1..=m {
            for j in 1..=n {
                dp[i][j] = if a[i - 1] == b[j - 1] {
                    dp[i - 1][j - 1]
                } else {
                    1 + dp[i - 1][j - 1].min(dp[i - 1][j]).min(dp[i][j - 1])
                };
            }
        }
        dp[m][n]
    }
}

Rust · runnable

function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        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]);
      }
    }
  }
  return dp[m][n];
}

TypeScript · runnable

1D Rolling Buffer

TimeO(m · n)

SpaceO(min(m, n))

Recommended

Same recurrence, one row of memory plus a prev_diag cache. Put the shorter string on the inner axis to minimize the row width.

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        // Iterate the shorter string on the inner axis.
        let (a, b) = if word1.len() < word2.len() {
            (word2.as_bytes(), word1.as_bytes())
        } else {
            (word1.as_bytes(), word2.as_bytes())
        };
        let n = b.len();
        let mut dp = vec![0i32; n + 1];
        for j in 0..=n {
            dp[j] = j as i32;
        }
        for (i, &ai) in a.iter().enumerate() {
            let mut prev_diag = dp[0];
            dp[0] = (i + 1) as i32;
            for j in 1..=n {
                let saved = dp[j];
                dp[j] = if ai == b[j - 1] {
                    prev_diag
                } else {
                    1 + prev_diag.min(dp[j]).min(dp[j - 1])
                };
                prev_diag = saved;
            }
        }
        dp[n]
    }
}

Rust · runnable

function minDistance(word1: string, word2: string): number {
  // Iterate the shorter string on the inner axis.
  const [a, b] = word1.length < word2.length ? [word2, word1] : [word1, word2];
  const n = b.length;
  const dp = new Array<number>(n + 1);
  for (let j = 0; j <= n; j++) dp[j]= j;
  for (let i= 0; i < a.length; i++) {
    let prevDiag= dp[0];
    dp[0]= i + 1;
    for (let j= 1; j <= n; j++) {
      const saved= dp[j];
      if (a[i]= b[j - 1]) {
        dp[j]= prevDiag;
      } else {
        dp[j]= 1 + Math.min(prevDiag, dp[j], dp[j - 1]);
      }
      prevDiag= saved;
    }
  }
  return dp[n];
}

TypeScript · runnable

Trace

2D fill on word1 = "horse", word2 = "ros":

i (word1[i-1])	j=0 ''	j=1 'r'	j=2 'o'	j=3 's'
0 ''	0	1	2	3
1 'h'	1	1	2	3
2 'o'	2	2	1	2
3 'r'	3	2	2	2
4 's'	4	3	3	2
5 'e'	5	4	4	3

Return dp[5][3] = 3. ✓

Edge cases

One string empty — return the other string's length. Base cases handle this.
Identical strings — return 0. Diagonal matches propagate zero cost all the way.
Completely disjoint — return max(m, n). Every position costs either a replace (if aligned) or insert/delete (if not).
Unicode — Rust byte indexing panics on multi-byte chars. LC inputs are ASCII; be explicit if you lift this.

💡

Tip

The three edit operations each map to one of the three neighbor transitions. Once you see this, remembering the recurrence is automatic: left = insert, up = delete, diagonal = replace (or match). The symmetric choice at each mismatch is what makes Edit Distance the reference algorithm for approximate string matching — diff tools, spell checkers, DNA alignment all descend from this recurrence.

Takeaway

Edit Distance is the aggregator-swapped twin of LCS. Both are 2D string DPs with a match branch and a mismatch branch; the difference is max(+1, skip) for LCS vs. min(+1 × 3 neighbors) for Edit Distance.

The row-collapse with prev_diag template you wrote for LCS reuses here without modification — and will reuse again in #583 Delete Operation for Two Strings and #712 Minimum ASCII Delete Sum. At this point in Stage-3, any "two strings, per-position decision" prompt should trigger the same reflex: 2D table, three neighbors, aggregate, collapse to 1D.

Medium#1143

Longest Common Subsequence

The classic 2D string DP. Understand match vs. skip transitions.

More in 2D DP

Medium#62

Unique Paths

dp[i][j] = dp[i-1][j] + dp[i][j-1]. Grid DP starting point.

Medium#1143

Longest Common Subsequence

The classic 2D string DP. Understand match vs. skip transitions.

Medium#416

Partition Equal Subset Sum

0/1 Knapsack. dp[j] = can we make sum j? Space-optimize to 1D.

Medium#494

Target Sum

Count knapsack variant. Or transform to subset sum with math.

View #72 on LeetCode