Edit Distance
DSA · Dynamic Programming
Theory
Edit distance (Levenshtein distance) is the minimum number of single-character insertions, deletions and substitutions needed to turn one string into another. "kitten" becomes "sitting" in 3 edits. The DP table dp[i][j] holds the edit distance between the first i characters of word A and the first j characters of word B. If the current characters match, dp[i][j] = dp[i-1][j-1]; otherwise it is 1 plus the minimum of deleting (dp[i-1][j]), inserting (dp[i][j-1]) or replacing (dp[i-1][j-1]). The first row and column are base cases: converting to or from an empty string costs i or j edits. The algorithm runs in O(m * n) time and can use O(n) memory by keeping only two rows.
Why we use it
It powers spell checkers, fuzzy search, DNA sequence comparison, plagiarism detection and data cleaning (matching "Mumbai" with "Mumbay").
When to use it
Use it to measure how similar two strings are, or to suggest corrections. For very long strings or huge datasets, use approximate or indexed methods.
How it works
- dp[i][0] = i, dp[0][j] = j
- For each i, j
- Characters equal? Yes: dp[i][j] = dp[i-1][j-1]. No: 1 + min(delete, insert, replace).
- Return dp[m][n]
Syntax
dp[i][j] = dp[i-1][j-1] if a[i-1] == b[j-1]
= 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) otherwise
Time O(m*n)Example
def edit_distance(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
for a, b in [("kitten", "sitting"), ("Mumbai", "Mumbay"), ("data", "data"), ("", "abc")]:
print(f"{a!r} -> {b!r}: {edit_distance(a, b)}")
words = ["python", "pandas", "spark", "pyspark"]
typo = "pyhton"
print("Did you mean:", min(words, key=lambda w: edit_distance(typo, w)))Key points
- Counts minimum insert, delete and replace operations
- Classic 2D DP: O(m * n) time
- Two rows are enough for O(n) memory
- Used in spell check and fuzzy matching