Questions: Edit Distance: Levenshtein Distance and DP

Question 1

You are computing the edit distance between 'CA' and 'ABC'. What is dp[1][1] — the edit distance between the prefix 'C' and the prefix 'A'?

• A. 0, because both substrings have length 1
• B. 1, because one replacement transforms 'C' into 'A'
• C. 2, because you must delete 'C' and then insert 'A'
• D. Cannot be determined without computing the full table first

Answer: (B)

dp[1][1] asks: what is the minimum number of edits to turn the 1-character string 'C' into the 1-character string 'A'? Since C ≠ A, you apply the recurrence: min(dp[0][0]+1, dp[0][1]+1, dp[1][0]+1) = min(0+1, 1+1, 1+1) = 1. One replacement suffices. Option C represents a misunderstanding — delete-then-insert costs 2, but the recurrence already finds the cheaper replacement path. Option A mistakes 'same length' for 'same content.'

Question 2

A programmer wants to reduce the O(mn) space of the edit distance algorithm. They realize they can use only two rows instead of the full table. Which property of the recurrence makes this optimization valid?

• A. The recurrence is linear, so intermediate results can be discarded
• B. Each cell dp[i][j] depends only on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1] — the previous row and the current row so far
• C. The strings must have equal length for the optimization to work
• D. The optimization only applies when using memoization rather than tabulation

Answer: (B)

The recurrence dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1) looks at exactly three neighbors: directly above (i-1, j), diagonally above-left (i-1, j-1), and directly left (i, j-1). No cell further back than row i-1 is ever needed. This means you can fill row i using only row i-1 and the partially-filled row i, then discard all earlier rows. With care, even the two-row space can be reduced to O(min(m,n)) using a single rolling array.

Question 3

The edit distance between two strings is symmetric: dist('kitten', 'sitting') equals dist('sitting', 'kitten').

• T. True
• F. False

Answer: True

Every insertion in one direction corresponds to a deletion in the reverse direction, and replacements are symmetric. Any sequence of edits transforming A into B can be reversed to transform B into A with the same number of operations. This symmetry is not immediately obvious from the recurrence (the table is not symmetric), but the optimal cost works out equal in both directions.

Question 4

Edit distance and longest common subsequence (LCS) measure the same underlying relationship between strings — one just counts edits while the other counts shared characters.

• T. True
• F. False

Answer: False

Although both relate to string similarity, they measure different things with different operations. LCS counts the length of the longest subsequence common to both strings and only uses matches (characters that appear in order in both). Edit distance counts the minimum edits using insert, delete, and replace. A pair of strings can have a long LCS yet still require many edits (e.g., if one string has many extra characters), and the relationship between the two measures is not a simple formula.

Question 5

Explain what each of the three terms in the edit distance recurrence — dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1 — represents when A[i] ≠ B[j]. Why does each term add exactly 1?

Model answer: dp[i-1][j-1]+1 represents replacing A[i] with B[j]: you already paid to align the first i-1 characters of A with the first j-1 characters of B, and now pay 1 to swap the mismatched characters. dp[i-1][j]+1 represents deleting A[i]: you pay 1 to remove A[i], then the cost reduces to aligning the first i-1 characters of A with all j characters of B. dp[i][j-1]+1 represents inserting B[j]: you pay 1 to insert B[j] at this position, then the cost reduces to aligning all i characters of A with the first j-1 characters of B. Each adds exactly 1 because each operation is one edit.

The key insight is that each cell reference corresponds to a specific operation: diagonal = replace, up = delete from A, left = insert from B. Taking the minimum selects the cheapest of the three ways to handle the mismatch. When A[i] = B[j], no edit is needed so dp[i][j] = dp[i-1][j-1] with no +1 — the diagonal move is free.