AlgoMaster Logo

Edit Distance

hardFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We need to find the minimum number of single-character edits (insertions, deletions, or replacements) to transform one string into another. This metric is the Levenshtein distance, used in spell checkers, diff tools, and DNA sequence alignment.

At each position we have three choices, and the best choice at one position depends on what we do at the others. A greedy pick of the locally cheapest edit can fail: replacing a character might look good now but force extra edits later. The decisions overlap, which points toward dynamic programming.

One property drives every approach below. If the last characters of both strings match, those characters need no edit, and the problem reduces to the two prefixes without them. If they differ, we try all three operations and take the minimum.

Key Constraints:

  • 0 <= word1.length, word2.length <= 500 --> An O(m * n) solution does at most about 250,000 operations, and a 500x500 int table is well within memory. Both rule in the standard DP approaches and rule out the exponential brute force as a final answer.
  • word1 and word2 consist of lowercase English letters --> Plain character comparison is enough; no Unicode or case handling.

Approach 1: Recursion (Brute Force)

Intuition

Solve the problem recursively, comparing the strings from the end. If the last characters match, no edit is needed for them, so recurse on the remaining prefixes. If they differ, try all three operations and take the minimum:

  • Insert a character at the end of word1 to match word2's last character. This "uses up" the last character of word2, so recurse on word1[0..i] and word2[0..j-1].
  • Delete the last character of word1. Recurse on word1[0..i-1] and word2[0..j].
  • Replace the last character of word1 with word2's last character. Both last characters are now handled, so recurse on word1[0..i-1] and word2[0..j-1].

The base cases: if word1 is empty, we need j insertions; if word2 is empty, we need i deletions.

Algorithm

  1. Define a recursive function solve(i, j) that returns the edit distance between word1[0..i-1] and word2[0..j-1].
  2. Base cases: if i == 0, return j. If j == 0, return i.
  3. If word1[i-1] == word2[j-1], the characters match, return solve(i-1, j-1).
  4. Otherwise, return 1 + min(solve(i-1, j), solve(i, j-1), solve(i-1, j-1)) corresponding to delete, insert, and replace.

Example Walkthrough

1solve(5,3): word1[4]='e' != word2[2]='s', try all 3 ops
0
h
1
o
2
r
3
s
4
e
i=5
1/4

Code

The recursion recomputes the same subproblems many times, yet there are only (m+1) * (n+1) unique states. Caching each result removes the duplication.

Approach 2: Top-Down DP (Memoization)

Intuition

The result of solve(i, j) depends only on i and j, and there are at most (m+1) * (n+1) distinct pairs. Storing each result the first time it is computed turns every later call with the same arguments into a table lookup, so each state is solved once.

The recursive structure stays identical to Approach 1. The only addition is a cache checked at the top of the function and written before returning.

Algorithm

  1. Create a 2D memo table of size (m+1) x (n+1), initialized to -1.
  2. Define solve(i, j) the same way as Approach 1.
  3. Before computing, check if memo[i][j] is already set. If so, return it immediately.
  4. After computing the result, store it in memo[i][j] before returning.

Example Walkthrough

1solve(5,3): check memo[-1], compute: 'e'!='s', try 3 ops
0
h
1
o
2
r
3
s
4
e
i=5
1/4

Code

Memoization removes the redundant work but keeps the overhead of recursive calls and a deep stack. The next approach computes every subproblem bottom-up in a 2D array, iteratively.

Approach 3: Bottom-Up DP (Tabulation)

Intuition

Instead of letting recursion decide which subproblems to solve, fill a 2D table from smaller subproblems to larger ones. Define dp[i][j] as the edit distance between word1[0..i-1] and word2[0..j-1]. The recurrence matches Approach 1, but now we iterate through all (i, j) pairs in order.

The base cases fill the first row and first column: dp[0][j] = j (inserting j characters into an empty string) and dp[i][0] = i (deleting i characters to reach an empty string). Each cell depends on its left neighbor, top neighbor, and top-left diagonal, so filling row by row, left to right, guarantees those three are already computed when a cell is reached.

Algorithm

  1. Create a 2D table dp of size (m+1) x (n+1).
  2. Initialize base cases: dp[i][0] = i for all i, and dp[0][j] = j for all j.
  3. For each cell dp[i][j] (1-indexed):
    • If word1[i-1] == word2[j-1], set dp[i][j] = dp[i-1][j-1] (no edit needed).
    • Otherwise, set dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
  4. Return dp[m][n].

Example Walkthrough

1Base cases: dp[i][0]=i (delete i chars), dp[0][j]=j (insert j chars)
0
1
2
3
0
0
1
2
3
1
1
0
0
0
2
2
0
0
0
3
3
0
0
0
4
4
0
0
0
5
5
0
0
0
1/7

Code

The full table costs O(m * n) space, but each row depends only on the previous row. The next approach keeps a single row and reduces space to O(min(m, n)).

Approach 4: Space-Optimized DP

Intuition

Since dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1], only the current and previous rows are ever needed. A single 1D array can hold both if we preserve the one value that overwriting would destroy.

Filling left to right, dp[j-1] already holds the current row's left neighbor, and dp[j] still holds the previous row's value at column j (the top neighbor). The diagonal dp[i-1][j-1] is the previous row's value at column j, which was overwritten on the prior iteration, so we save it in prev before that happens.

Algorithm

  1. Create a 1D array dp of size (n+1), initialized with dp[j] = j for all j (base case for row 0).
  2. For each row i from 1 to m:
    • Save dp[0] as prev (the diagonal for column 1). Set dp[0] = i (base case for column 0).
    • For each column j from 1 to n:
      • Save the current dp[j] as temp (it will become the diagonal for the next column).
      • If characters match, dp[j] = prev.
      • Otherwise, dp[j] = 1 + min(prev, dp[j], dp[j-1]).
      • Update prev = temp.
  3. Return dp[n].

Example Walkthrough

1Initial dp (base case row 0): dp[j] = j
0
0
1
1
2
2
3
3
1/7

Code