Course contentsShow
← Computer Science
Lesson 927 of 2,87222. Dynamic ProgrammingFree lesson

Edit Distance (Levenshtein Distance)

Calculate minimum edits (insert, delete, replace) to transform one string into another using DP.

Edit Distance (Levenstein Distance)

What you'll learn: You'll discover how to calculate the minimum number of single-character edits needed to transform one string into another using dynamic programming.

The Problem

Imagine you're building a spell-checker or autocorrect feature. You need to measure how "different" two words are. Edit distance (also called Levenshtein distance) counts the minimum number of operations—insert, delete, or replace a character—needed to change one string into another.

For example, transforming "kitten" → "sitting" requires:

  1. Replace 'k' with 's' → "sitten"
  2. Replace 'e' with 'i' → "sittin"
  3. Insert 'g' at end → "sitting"

Total: 3 edits

Why Dynamic Programming?

This problem has optimal substructure: the edit distance between two strings depends on the edit distances of their prefixes. It also has overlapping subproblems: when comparing "abc" and "xyz", we might compute the distance between "ab" and "xy" multiple times through different paths.

The Core Idea

Define dp[i][j] = minimum edits to transform the first i characters of string A into the first j characters of string B.

Base cases:

  • dp[0][j] = j (insert j characters)
  • dp[i][0] = i (delete i characters)

Transition:

  • If A[i-1] == B[j-1]: characters match, so dp[i][j] = dp[i-1][j-1]
  • Otherwise, take the minimum of:
    • dp[i-1][j] + 1 (delete from A)
    • dp[i][j-1] + 1 (insert into A)
    • dp[i-1][j-1] + 1 (replace)

You fill a 2D table bottom-up, and dp[len(A)][len(B)] gives your answer.

Key Takeaway: Edit distance uses a 2D DP table where each cell represents the minimum edits for string prefixes, building from base cases of empty strings to the full transformation cost.