Edit Distance

Free with account Updated Nov 19, 2026 · 5 min read
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

    "sun" becomes "snow" in 3 edits: delete u, insert o, insert w.
    "sun" becomes "snow" in 3 edits: delete u, insert o, insert w.
    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

    1. Do all three operations cost 1? (Here: yes. Weighted costs change only the + 1s.)
    2. Is swapping two adjacent letters one edit? (Here: no. That is the Damerau variant.)
    3. Do you need the list of edits, or only the count?
    4. How long are the strings? 500 × 500 is fine; a million each is not.