vizlearn

Edit distance (Levenshtein)

Interview QuestionsBy Updated

A table where dp[i][j] is the cost of turning the first i characters of one string into the first j of the other. Each cell is either the diagonal unchanged (characters match) or one more than the cheapest of its three neighbours. O(m·n) time and space, reducible to O(min(m, n)).

Overview

What each neighbour means

The three options are not arbitrary; each is one edit:

Diagonal (dp[i-1][j-1]) — substitute one character for the other. Free when they already match.

Up (dp[i-1][j]) — delete a character from the first string.

Left (dp[i][j-1]) — insert a character into the first string.

Being able to say which is which is what separates understanding the recurrence from having memorised it.

StringsCoding problemHard

Step through it

What to watch

  • The edges are free to fill: i deletions to reach the empty string.
  • A match copies the diagonal — no cost added at all.
  • Each neighbour corresponds to one specific edit.

Say this out loud

"Classic DP. dp[i][j] is the cost for the two prefixes. If the characters match it's the diagonal; otherwise it's 1 plus the min of diagonal, left and up - substitute, insert, delete. O(m·n), and you only need two rows so space can be O(min(m,n))."

Edit distance (Levenshtein)

What is the minimum number of insertions, deletions and substitutions to turn one string into another?

The base cases

Row 0 and column 0 are the edges: turning a prefix of length i into the empty string costs i deletions, and building a prefix of length j from nothing costs j insertions. Filling them with zeros instead is the most common mistake, and it produces answers that are too small.

Cutting the space

Each cell depends only on the row above and the cell to its left, so the whole table is never needed at once — two rows suffice, and iterating over the shorter string makes it O(min(m, n)).

The trade is that you can no longer walk the table backwards to recover the actual sequence of edits. If the question asks which edits, keep the full table; if it asks only for the count, the two-row version is strictly better.

Run it in Python

The full table printed for a small pair so the shape is visible, the two-row version checked against it, and the zeroed-base-case bug producing a confidently wrong answer.

edit_distance.pyPython 3
Output
How the code works
  1. dp[i][0] = iThe base case people zero out by accident. Turning a prefix into the empty string costs one deletion per character, and starting from zero makes every answer too small.
  2. dp[i][j] = dp[i - 1][j - 1]A match costs nothing at all — it copies the diagonal rather than adding to it. Adding 1 here is the other common slip.
  3. min(diagonal, up, left)Substitute, delete, insert, in that order. Being able to name which neighbour is which edit is what shows you understand the recurrence rather than remember it.
  4. previous = currentThe two-row version. Each cell needs only the row above and the cell to its left, so the full table is never required — unless you want to reconstruct the edits.
Change one thing
  • Swap the argument order. The distance is symmetric, and watching the table transpose is a good check that you have the axes right.
  • Add a fourth move for transposition (swapping adjacent characters). That turns it into Damerau-Levenshtein, which is what spell checkers actually use.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. In the DP table, the cell above dp[i][j] corresponds to which edit?
  2. Filling row 0 and column 0 with zeros instead of 0..n gives:
  3. The space can be reduced to O(min(m, n)) because:





 Cheat sheet
Edit distance (Levenshtein)
A table where dp[i][j] is the cost of turning the first i characters of one string into the first j of the other. Each cell is either the diagonal unchanged (characters match) or one more than the cheapest of its three neighbours. O(m·n) time and space, reducible to O(min(m, n)).
INTERVIEW · vizlearn.in/interview/edit-distance.html
More in Interview
InterviewMinimum window substringInterviewWhat is a Python list underneath?InterviewWhy does [[0]*3]*3 break?InterviewWhy is `in` slow on a list but fast on a set?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact