Algorithm

Edit Distance

Dynamic Programming Pattern

Edit Distance

You are given two strings word1 and word2. In a single operation you may insert one character into word1, delete one character from word1, or replace one character of word1 with any other character. Return the minimum number of operations needed to turn word1 into word2. Either string may be empty.

CONSTRAINTS
  • 0 ≤ word1.length, word2.length ≤ 500
  • Both strings consist of lowercase English letters
  • The three permitted operations are insert, delete and replace, each costing 1
EXAMPLE 1
Input: word1 = "horse", word2 = "ros"
Output: 3
Replace h with r, delete the first r, delete the e. Three single-character operations, and no sequence of two can bridge a five-character string to a three-character one while also fixing the leading letter.
EXAMPLE 2
Input: word1 = "intention", word2 = "execution"
Output: 5
Five characters must change or be removed; the shared tail ention aligns for free once the front is fixed.
EXAMPLE 3
Input: word1 = "", word2 = "abc"
Output: 3
Starting from nothing, each of the three target characters must be inserted separately.
EXAMPLE 4
Input: word1 = "abc", word2 = "abc"
Output: 0
The strings already agree at every position, so no operation is needed.
EXAMPLE 5
Input: word1 = "a", word2 = "ab"
Output: 1
Inserting b at the end is enough. Replacing the a would not help, since the a is already correct and the string would still be one character short.
Do all three operations cost the same?
Yes, each costs 1 here. If an interviewer gives them different prices, the recurrence keeps its exact shape and only the added constant changes per branch — the structure is unaffected.
Can I insert or delete anywhere in the string, or only at the ends?
Anywhere. That freedom is what lets the alignment view work: since position is unconstrained, we can always assume edits happen exactly where the two pointers currently sit.
Can either string be empty?
Yes, and it is the cleanest base case: turning an empty string into one of length m costs exactly m insertions. Any solution that crashes or returns 0 on an empty input has the base case wrong.
Does it matter which string I am allowed to edit?
No, the answer is the same either way. An insertion into the first string is a deletion from the second, so the distance is symmetric. Saying this out loud is a good way to show you understand the operations rather than just the formula.
Is a swap of two adjacent characters a single operation?
Not here — swapping counts as two operations. There is a well-known variant, the Damerau-Levenshtein distance, that adds transposition as a fourth move, so it is worth confirming which one is being asked for.
What we are counting

You may edit the first string one character at a time, and each edit costs exactly one. Insert a character anywhere, delete a character from anywhere, or replace one character with another. Question: what is the smallest number of edits that turns word1 into word2?

This number is called the Levenshtein distance, and it is what powers spell-checkers, fuzzy search and DNA sequence comparison. "horse" to "ros" takes 3: replace the h with r giving "rorse", delete the r giving "rose", delete the e giving "ros".

One clarification that saves a lot of confusion: although the operations are described as acting on word1, an insertion into word1 and a deletion from word2 are the same move viewed from opposite sides. The distance is symmetric — turning word1 into word2 costs exactly as much as the reverse.

Why you cannot search for the edits directly

The obvious plan is to try every sequence of edits and keep the shortest. At every position you have three choices, and strings are up to 500 characters, so the number of edit sequences is astronomically large. Worse, edits change the string underneath you, so it is not even clear what "position" means after a few of them.

The reframe that dissolves this: stop thinking about editing a string and start thinking about aligning two strings. Walk both strings from the left simultaneously and decide, at each step, how the current characters correspond. Under that view, editing never mutates anything — it just decides how the pointers advance.

The state: two prefixes

State Definition: f(i, j) is the fewest operations to turn the first i characters of word1 into the first j characters of word2.

The recurrence

Look at the last character on each side, word1[i-1] and word2[j-1].

If they are the same, they already agree. Pay nothing and drop both: f(i-1, j-1). (Editing a pair that already matches never helps.)

If they differ, you must do one edit, and there are exactly three ways to make progress. Each costs 1, and each drops different characters:

- Replace word1's last character with word2's. Now they agree, so drop both: 1 + f(i-1, j-1).
- Delete word1's last character. It is gone, so drop it from word1 while word2 still needs its character: 1 + f(i-1, j).
- Insert word2's last character onto word1. That satisfies word2's character, so drop it from word2 while word1 is unchanged: 1 + f(i, j-1).

Take the cheapest:

f(i, j) = 1 + min( f(i-1, j-1), f(i-1, j), f(i, j-1) ) when the characters differ.

Crucial Notethe moves for delete and insert are the ones people mix up. The test that settles it: every edit must use up a character. Delete uses a character of word1, so i drops. Insert satisfies a character of word2, so j drops. Replace uses one from each, so both drop. If a move leaves both counts unchanged, the recursion never ends.

Base cases:

- f(0, j) = j — word1 is empty, so insert the j remaining characters of word2.
- f(i, 0) = i — word2 is empty, so delete the i remaining characters of word1.

We start with the full lengths: f(n, m).

Recursion and memo
python
def min_distance(word1, word2):
    n, m = len(word1), len(word2)
    memo = {}

    def f(i, j):
        if i == 0: return j          # insert the rest of word2
        if j == 0: return i          # delete the rest of word1
        if (i, j) in memo: return memo[(i, j)]
        if word1[i - 1] == word2[j - 1]:
            result = f(i - 1, j - 1)          # free
        else:
            result = 1 + min(f(i - 1, j - 1),  # replace
                             f(i - 1, j),      # delete from word1
                             f(i, j - 1))      # insert into word1
        memo[(i, j)] = result
        return result

    return f(n, m)

n × m states, constant work each: O(N × M) time and space. For 500-character strings that is 250000 cells.

The table from the recurrence

Let dp[i][j] hold what f(i, j) returned, and swap calls for reads. The base cases are not zeros this time — they go into the first row and first column: dp[0][j] = j and dp[i][0] = i. Every read points at a smaller i or j, so both loops run upward from 1. The answer is dp[n][m]:

python
def min_distance(word1, word2):
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for j in range(m + 1):
        dp[0][j] = j                 # word1 empty: insert the rest
    for i in range(n + 1):
        dp[i][0] = i                 # word2 empty: delete the rest

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],
                                   dp[i - 1][j],
                                   dp[i][j - 1])

    return dp[n][m]
Two rows

A cell only ever reads its own row and the row above, so two rows suffice and the space drops to O(M):

python
def min_distance(word1, word2):
    n, m = len(word1), len(word2)
    prev = list(range(m + 1))                 # row 0: dp[0][j] = j
    for i in range(1, n + 1):
        cur = [0] * (m + 1)
        cur[0] = i                            # dp[i][0] = i
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1], prev[j], cur[j - 1])
        prev = cur
    return prev[m]
Worked Example:word1 = "horse", word2 = "ros"
Reading off the finished table, the cheapest alignment is:
- h vs r — differ. The winning branch is replace, costing 1 and moving both pointers. ("horse" → "rorse")
- o vs o — match, free, both advance.
- r vs s — differ. The winning branch is delete, costing 1 and moving only word1's pointer. ("rorse" → "rose")
- s vs s — match, free, both advance.
- e remains in word1 while word2 is exhausted, so the base case charges 1 deletion. ("rose" → "ros")

Total 3.

Now a pure-insert case, "" to "abc": the first base case fires immediately and returns 3. And a case where replace is not the answer, "a" to "ab": replacing would cost 1 and still leave a mismatch downstream; inserting b costs 1 and finishes. The table returns 1.

The family this belongs to

The reflex to build: whenever a problem compares or transforms two sequences, set up the (i, j) grid, then spend your thinking on just two questions — what happens on a match, and what is the full list of moves on a mismatch.

Weighted variants (a deletion costs 2, an insertion costs 3) change nothing structurally: you stop adding 1 and start adding the specific cost. Restricted variants (say only deletions are allowed) simply remove entries from the mismatch menu. The grid and the walk stay the same; only the moves and their costs change.

Exponential Try Every Edit Sequence
→
O(N × M) Time · O(N × M) Space Memoisation
→
O(N × M) Time · O(N × M) Space Tabulation
→
O(N × M) Time · O(min(N, M)) Space Two Rows