In an edit distance table over two contact names, what does dp[i][j] mean and what fills row 0?
answer
- count what the extra row buys you
- rows and columns are lengths, not slots
- row zero: building something from nothing
- cell (i,j) looks one character back
- answer lives in the far corner
basics
~20 sdp[i][j] is the edit distance between the first i characters of one name and the first j of the other — the indexes are prefix LENGTHS, not positions. Row 0 holds 0,1,2,...,j: turning nothing into a j-character prefix costs j insertions.
solid answer
~40 sThe table is `(m+1)` by `(n+1)` because the indexes count prefix lengths, including the empty prefix. `dp[i][j]` is the minimum number of insertions, deletions and replacements that turn the first `i` characters of the first name into the first `j` characters of the second. That gives free base cases: `dp[0][j] = j` (insert j characters into nothing), `dp[i][0] = i` (delete i characters), `dp[0][0] = 0`. The consequence people trip on is the off-by-one: at cell `(i,j)` the characters being compared are `a[i-1]` and `b[j-1]`, one index back, because length i means "through the character at index i-1". Equal characters copy the diagonal for free; unequal ones take `1 + min(diagonal, up, left)` for replace, delete and insert. The answer is `dp[m][n]`.
code
pseudocode · 13 linesm = length(a); n = length(b)
for i in 0..m: dp[i][0] = i # delete i characters
for j in 0..n: dp[0][j] = j # insert j characters
for i in 1..m:
for j in 1..n:
if a[i-1] == b[j-1]: # NOT a[i] / b[j]
dp[i][j] = dp[i-1][j-1] # free diagonal
else:
dp[i][j] = 1 + min(dp[i-1][j-1], # replace
dp[i-1][j], # delete from a
dp[i][j-1]) # insert into a
...
answer = dp[m][n]go deeper
Be ready to draw the grid and say what one cell means before writing any loop: distance between the first i characters and the first j characters. Then state row 0 as j and column 0 as i, and read the answer from the last cell.
Explain why the table is one bigger in each dimension and why the loop compares the characters one index back. Walk the three neighbour moves and name each as replace, delete and insert rather than reciting a min of three numbers.
Show that you know where this breaks in production: the off-by-one that silently misaligns, the normalization decision upstream of the table, and the fact that dropping rows to one saves memory without touching the quadratic running time.
Own the modelling question above the recurrence: whether all three operations should cost one, whether an adjacent-character swap should count as one edit or two, and whether a threshold-and-reject check is cheaper than a distance for the product you are actually building.
## What edit distance measures Edit distance (Levenshtein distance) is the minimum number of single-character edits — insert one character, delete one character, replace one character with another — needed to turn one string into another. In a contact-search "did you mean" feature it is the score behind offering *Katarzyna* when someone typed *Katarzina*: one replacement, distance 1. ## Why the indexes are lengths The dynamic-programming table has `m+1` rows and `n+1` columns for names of length `m` and `n`. The extra row and column are not padding: index 0 is the **empty prefix**, a real subproblem with a real answer. So `dp[i][j]` = the distance between the first `i` characters of `a` and the first `j` characters of `b`. Indexes are prefix *lengths*, and the range is `0..m` inclusive. This is the single most productive thing to say out loud in an interview, because everything else falls out of it: - **Base cases become trivial.** `dp[0][j] = j`: the only way to build a `j`-character prefix out of nothing is `j` insertions. `dp[i][0] = i`: the only way to reduce an `i`-character prefix to nothing is `i` deletions. `dp[0][0] = 0`. - **The final answer has an obvious address:** `dp[m][n]`, the bottom-right cell, the distance between both full strings. - **The comparison shifts by one.** When you are computing cell `(i,j)` you are deciding what to do with the *last* character of each prefix, which is `a[i-1]` and `b[j-1]`. Writing `a[i]` inside the loop is the classic shipped bug: it silently aligns the wrong pair and reads one past the end on the last row. ## The transitions If `a[i-1] == b[j-1]`, the last characters already agree, so nothing is spent: `dp[i][j] = dp[i-1][j-1]`. Otherwise you pay one edit and take the best of three smaller problems: | Move | Cell used | Meaning | |---|---|---| | replace | `dp[i-1][j-1]` | swap `a[i-1]` for `b[j-1]`, both prefixes shrink | | delete | `dp[i-1][j]` | drop `a[i-1]`, only the first prefix shrinks | | insert | `dp[i][j-1]` | add `b[j-1]`, only the second prefix shrinks | Each cell depends only on its up, left and up-left neighbours, so filling row by row, left to right, always finds its dependencies already computed. ## Cost, and the direction of the claim Filling the table is `O(m*n)` time and `O(m*n)` space. If you only need the *number* and never the alignment, one row plus a saved diagonal value suffices, which is `O(min(m,n))` space — but the time stays quadratic. Note also what the metric does *not* promise: it is symmetric only while insert and delete cost the same, and it counts edits, not perceptual similarity. Two names that look alike to a human can sit several edits apart. ## One practical trap on names Before the table exists, decide what counts as one character and normalize the text to that decision. If an accented letter is stored one way in the contact list and another way in the query box, the two spellings can be visually identical and still be several edits apart, and your "did you mean" quietly stops firing for exactly the users whose names need it most. That is a data-preparation decision, not a DP decision, but it lives immediately upstream of this table. ## What a good answer sounds like "`dp[i][j]` is the distance between the first `i` characters of one and the first `j` of the other. Row and column zero are the empty-prefix cases and fill with `j` and `i`. Inside the loop I compare `a[i-1]` to `b[j-1]`; equal is a free diagonal step, unequal is one plus the min of the three neighbours. Answer at `dp[m][n]`, quadratic time."
- Why is dp[0][j] equal to j rather than 0?Because row 0 means the first string contributes an empty prefix, and the only way to turn nothing into a j-character prefix is j insertions. Zero would claim an empty prefix already equals a non-empty one, which corrupts every cell that later reads from that row. Column 0 is the mirror image: i deletions.
- The table is filled row by row, left to right. Why is that order safe?Every cell reads only its up, left and up-left neighbours. Row-major order visits all three before reaching the cell, so each dependency is already final. Any order with that property works — column by column, or diagonal by diagonal, which is what parallel implementations use since a whole anti-diagonal is independent.
- If you only need the distance number, how much of the table do you actually keep?One row, plus a single saved value for the diagonal you are about to overwrite — O(min(m,n)) space if you orient the table so the shorter string drives the row width. Time stays O(m*n); dropping rows saves memory only. You lose the ability to reconstruct the alignment, since the discarded rows were the trail.
Think of it as a mileage chart between every pair of prefixes rather than between the two whole names: the corner you want is the last cell, and every earlier cell is a shorter trip you already paid for.
saying these in an interview costs you the question
- Says dp[i][j] compares the characters at index i and j
- Fills row 0 and column 0 with zeros
- Builds an m-by-n table with no empty-prefix row
- Reads the answer from dp[m-1][n-1]
- Calls the space O(m*n) unavoidable even when only the number is needed