How do you compute the edit distance between two strings?

Q: How do you compute the edit distance between two strings?

**Target Audience:** Beginners preparing for coding interviews — you need loops, lists and 2D lists. **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First You type **"horse"** but meant **"ros"** (it happens). Your phone's keyboard has to decide how "far apart" those two words are, so it can suggest the closest real word. The natural measure is: **how many single-letter fixes does it take?** A fix is one of three things — **insert** a letter, **delete** a letter, or **replace** one letter with another. "horse" becomes "ros" in three fixes: replace h with r (rors

The problem

Question presented to candidate: "Given two words, return the minimum number of operations to turn the first into the second, where an operation inserts, deletes or replaces one character. Explain your table, then code it in Python."

What a strong answer should cover:

The state dp[i][j] = fewest edits turning the first i characters of word1 into the first j of word2.
The base cases dp[i][0] = i and dp[0][j] = j (not zeros), and why.
The transition: equal characters copy the diagonal; otherwise 1 + min(diagonal = replace, up = delete, left = insert).
O(m·n) time and space; O(min(m, n)) space with two rows when only the number is needed; walking back for the edit script.
Python details: building the table with a list comprehension, min() over three values, and that difflib.SequenceMatcher is not a Levenshtein distance.

Clarifying questions expected:

Are all three operations allowed, and do they all cost 1?
Does swapping two adjacent characters count as one edit?
Do you need the edit operations or just the count?

Code / implementation expected: Yes — a bottom-up table in Python; mention the two-row optimisation and how to recover the operations.

dp
strings

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you need loops, lists and 2D lists.
Difficulty: Hard
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

You type "horse" but meant "ros" (it happens). Your phone's keyboard has to decide how "far apart" those two words are, so it can suggest the closest real word. The natural measure is: how many single-letter fixes does it take? A fix is one of three things — insert a letter, delete a letter,

The solution is hidden so you can try first

15 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonEdit distance table, distances and the edit script

Practice

PythonNaive recursion vs table, the LCS link, and two rows

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.