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:
- Replace 'k' with 's' → "sitten"
- Replace 'e' with 'i' → "sittin"
- 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, sodp[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.