Edit Distance Problem: How Would You Solve It?
Learn how to solve the edit distance (Levenshtein) problem with dynamic programming, the recurrence, and a Python implementation.
Expected Interview Answer
Edit distance (Levenshtein distance) is solved with dynamic programming: dp[i][j] holds the minimum number of insertions, deletions, and substitutions to turn the first i characters of one string into the first j characters of another, computed by comparing the last characters and taking the cheapest of three prior subproblems plus one edit, or zero extra cost if the characters already match.
The recurrence is dp[i][j] = dp[i-1][j-1] if the characters match, otherwise 1 + min(dp[i-1][j-1] for substitution, dp[i-1][j] for deletion, dp[i][j-1] for insertion). The base cases are dp[i][0] = i and dp[0][j] = j, representing deleting or inserting every remaining character when one string is empty. This runs in O(m*n) time and space for strings of length m and n, and the space can be compressed to O(min(m,n)) by keeping only two rows at a time since each cell only depends on the row above and the current row so far. Edit distance underlies spell checkers, DNA sequence alignment, and diff tools, and it generalizes to weighted variants where insert, delete, and substitute have different costs.
- Correctly handles insert, delete, and substitute in one unified recurrence
- O(m*n) time, reducible to O(min(m,n)) space with rolling rows
- Backtracking through the table reconstructs the actual edit sequence
- Directly powers spell-check, diff, and DNA alignment tools
AI Mentor Explanation
Turning one team's batting order into another team's batting order costs one move for every swap, insertion, or removal of a player needed, and the cheapest way to do it compares three options at each step: keep both players if they match position needs, or pay for one substitution, one drop, or one addition. Building a table of the cheapest transformation cost, row by row for one order and column by column for the other, lets you look up the answer for any prefix length using answers already computed for shorter prefixes. If the last two players already match perfectly, no extra cost is needed at that step, exactly mirroring a matching-character move in edit distance. This row-by-column table of minimum transformation costs is precisely how edit distance is computed.
Step-by-Step Explanation
Step 1
Define the state
dp[i][j] = min edits to turn the first i chars of s1 into the first j chars of s2.
Step 2
Set base cases
dp[i][0] = i (delete all), dp[0][j] = j (insert all).
Step 3
Apply the recurrence
If s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]; else 1 + min(substitute, delete, insert) from the three neighbors.
Step 4
Optimize space if needed
Keep only the previous and current row, since each cell only depends on the row above and current row so far.
What Interviewer Expects
- State the three operations (insert, delete, substitute) and the recurrence correctly
- Explain the base cases dp[i][0] and dp[0][j]
- Give O(m*n) time and mention the O(min(m,n)) space optimization
- Explain how to reconstruct the actual sequence of edits if asked
Common Mistakes
- Forgetting that matching characters cost zero extra (dp[i][j] = dp[i-1][j-1], not +1)
- Mixing up which neighbor corresponds to insert vs delete
- Not initializing the base-case row and column correctly
- Assuming the space optimization removes the ability to reconstruct edits (it does, unless the full table or extra bookkeeping is kept)
Best Answer (HR Friendly)
“Edit distance is about finding the fewest single-character insertions, deletions, and substitutions needed to turn one string into another, and I compute it by building a table where each cell reuses answers for shorter prefixes of both strings. Whenever the current characters already match, I don't pay any extra cost — I only pay when I actually need to substitute, insert, or delete a character.”
Code Example
def edit_distance(s1, s2):
m, n = len(s1), len(s2)
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 s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j - 1], # substitute
dp[i - 1][j], # delete
dp[i][j - 1], # insert
)
return dp[m][n]
print(edit_distance("kitten", "sitting")) # 3Follow-up Questions
- How would you reduce this to O(min(m,n)) space?
- How would you reconstruct the actual sequence of edits, not just the count?
- How would you weight insert, delete, and substitute differently?
- How does this relate to the longest common subsequence problem?
MCQ Practice
1. What is dp[i][j] when s1[i-1] equals s2[j-1]?
Matching characters require no extra edit, so the cost carries over unchanged from the diagonal neighbor.
2. What is the time complexity of the standard edit distance DP solution?
The table has (m+1) by (n+1) cells, each computed in O(1), giving O(m*n) time.
3. What do dp[i][0] and dp[0][j] represent in the edit distance table?
dp[i][0]=i means deleting all i characters of s1; dp[0][j]=j means inserting all j characters to build s2 from empty.
Flash Cards
What is the edit distance recurrence when characters match? — dp[i][j] = dp[i-1][j-1], no extra cost.
What is the edit distance recurrence when characters differ? — 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) for substitute, delete, insert.
What is the time and space complexity? — O(m*n) time, reducible to O(min(m,n)) space with rolling rows.
Name one real application of edit distance. — Spell checkers (also diff tools and DNA sequence alignment).