Edit Distance
On this page
Problem statement
Given two strings, return the smallest number of single-character edits that turn the first into the second. An edit is inserting one character, deleting one character, or replacing one character with another.
This is the most-asked 2D DP. It is also used in practice: spell checkers, diff tools and fuzzy search all rely on it. Original problem: LeetCode 72.
Example

Input: a = "sun", b = "snow"
Output: 3 # delete u, insert o, insert w
Input: a = "cache", b = "catch"
Output: 2 # insert t after "ca", delete the final e
Input: a = "", b = "abc"
Output: 3
Constraints (assumed)
- 0 ≤ length of each string ≤ 500.
- Lowercase English letters.
What this question tests
- Defining a 2D state over two prefixes and naming what each neighbour means.
- Getting the base row and column right.
- Optional depth: the two-row memory optimisation and rebuilding the actual edit list.
Questions to ask first
- Do all three operations cost 1? (Here: yes. Weighted costs change only the
+ 1s.) - Is swapping two adjacent letters one edit? (Here: no. That is the Damerau variant.)
- Do you need the list of edits, or only the count?
- How long are the strings? 500 × 500 is fine; a million each is not.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.