Edit Distance Step by Step
Insert, delete, replace to transform.
Edit Distance Step by Step is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Edit Distance Measures
Edit distance is the fewest single-character edits to turn one string into another. It scores how different two words really are.
The Three Operations
You may insert, delete, or replace one character per edit. Each operation costs exactly one in the standard problem.
Define the State
Let dp[i][j] be the edits to change the first i characters of A into the first j characters of B.
Free Match
If the current characters already match, no edit is needed. You simply carry the diagonal value straight down.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Otherwise, Pay One
When characters differ, you take the cheapest neighbor and add one edit. That min plus one covers all three operations.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Which Neighbor Is Which
The cell above is a delete, the cell left is an insert, and the diagonal is a replace. The min just picks the cheapest.
Empty-String Base Cases
Turning a length-i string into empty needs i deletes. So fill the first row and column with 0, 1, 2, and so on.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jSize the Table
Use an n+1 by m+1 grid so the empty prefixes get their own row and column. This padding keeps the loops simple.
dp = [[0] * (m+1) for _ in range(n+1)]Fill in Order
Loop i and j upward from 1. Every cell depends only on already-filled neighbors above, left, and diagonal.
for i in range(1, n+1):
for j in range(1, m+1):
...Read the Distance
The minimum number of edits ends up in the corner. Your answer is dp[n][m] after the table is complete.
distance = dp[n][m]Cost and Variants
This runs in O(n times m) time. Real tasks may charge different costs per operation, but the same recurrence still works.
Quick Check
Characters A[i-1] and B[j-1] differ. Which recurrence gives the edit distance?
Recap: Edit Distance
Match means carry the diagonal; mismatch means 1 plus the min of three neighbors. Seed the borders, and read dp[n][m]. ✏️
Frequently asked questions
Is the “Edit Distance Step by Step” lesson free?
Yes — the full text of “Edit Distance Step by Step” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Edit Distance Step by Step”?
Insert, delete, replace to transform. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Edit Distance Step by Step” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Path Counting on a Grid
- Minimum Path Sum with Obstacles
- Longest Common Subsequence
- Edit Distance Step by Step