← DSA Atlas
Dedicated problem page · #72

Edit Distance

MediumTwo-Dimensional Dynamic ProgrammingSequence-alignment grid DP2D dynamic programming (Levenshtein distance)
Solve on LeetCode ↗
72
MediumTwo-Dimensional Dynamic Programming2D dynamic programming (Levenshtein distance)Sequence-alignment grid DP

Edit Distance

Given two strings word1 and word2, return the minimum number of single-character operations required to convert word1 into word2. The allowed operations are insert a character, delete a character, and replace a character.

Open official problem prompt ↗
In plain English

We want the cheapest sequence of single-character edits that rewrites word1 as word2.

Picture it like this

Like a spell-checker measuring how far a typo is from a dictionary word by counting the fewest keystroke fixes.

Example
Input
word1 = "horse", word2 = "ros"
Output
3
Why
horse -> rorse (replace h->r) -> rose (delete r) -> ros (delete e) uses three operations, and none is shorter.
Constraints
0 <= word1.length, word2.length <= 500word1 and word2 consist of lowercase English letters.
Pattern lesson

See the pattern, then code

Sequence-alignment grid DP
Recognition clue

Transforming one string into another with per-character insert/delete/replace costs is the textbook edit-distance grid DP.

↗
Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Aligning prefixes, if the last characters match nothing is spent; otherwise the last move is one of insert, delete, or replace, each reducing the problem to a slightly smaller prefix pair, so take the cheapest.

New words, made simpleKnow these before the algorithm
Edit operation
Insert, delete, or replace exactly one character.
Levenshtein distance
The minimum number of such edits between two strings.
Base case
Turning a string into empty costs its length (all deletions), and vice versa (all insertions).
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force recursion

Exponential; the same prefix pairs are recomputed endlessly.

At each step branch into insert, delete, replace, or match.

Time O(3^(m+n))Space O(m+n)
Best choice2D bottom-up DP

Each subproblem solved once; standard optimal solution.

Fill an (m+1) x (n+1) table of prefix distances with initialized borders.

Time O(m*n)Space O(m*n)
The rule we keep true

Invariant

dp[i][j] holds the exact minimum edit distance between word1[:i] and word2[:j] when read by later cells.

Why this is correct

Reasoning

Any optimal edit script's final operation on the current prefixes must be a match, insert, delete, or replace; each maps to a specific smaller cell. Because those cases are exhaustive and the borders are correct, the minimum over them is optimal by induction on prefix size.

The algorithm in three movesSay these aloud before coding
1Define dp[i][j] = edits to turn word1[:i] into word2[:j]

dp base row = 0..3

2Seed dp[i][0]=i (delete all) and dp[0][j]=j (insert all)

mismatch h/r -> replace

3If characters match, copy the diagonal dp[i-1][j-1]

dp[5][3] = 3

4Otherwise take 1 + min(delete dp[i-1][j], insert dp[i][j-1], replace dp[i-1][j-1])

5Return dp[m][n]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
replace h->r0
delete r1
delete e2
1 · Readempty prefixes
2 · AskHow much to reach empty?
3 · Update staterow 0 = 0,1,2,3; col 0 = 0,1,2,3,4,5
4 · Resultbase cases set
Key takeaway

The three operations that turn horse into ros, one per highlighted cell.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-8Initialize borders

    Converting to/from an empty string costs one edit per remaining character.

  2. 2
    Lines 11-12Free match

    Equal characters need no operation, so inherit the diagonal.

  3. 3
    Lines 13-14Three-way minimum

    delete = dp[i-1][j], insert = dp[i][j-1], replace = dp[i-1][j-1]; add one for the operation.

  4. 4
    Lines 15Return

    Bottom-right cell spans both full strings.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Either string empty returns the other's length
  • Identical strings return 0
  • Completely different strings of equal length return that length (all replacements)
!

Common beginner mistakes

  • Forgetting to initialize both borders, which corrupts every later cell
  • Mixing up which neighbor is insert vs delete
  • Adding a cost on a character match
Check your understanding

Why does a character match copy dp[i-1][j-1] with no +1 rather than taking a min with its neighbors?

More in Two-Dimensional Dynamic Programming

#1143Longest Common SubsequenceSequence-alignment grid DP#10Regular Expression MatchingPattern-matching grid DP with star lookback#44Wildcard MatchingGlob-matching grid DP#62Unique PathsGrid path-counting DP#63Unique Paths IIGrid path-counting DP with obstacles#64Minimum Path SumGrid path DP (right/down accumulation)