72. Edit Distance - Explanation

Description

You are given two strings word1 and word2, each consisting of lowercase English letters.

You are allowed to perform three operations on word1 an unlimited number of times:

Insert a character at any position
Delete a character at any position
Replace a character at any position

Return the minimum number of operations to make word1 equal word2.

Example 1:

Input: word1 = "monkeys", word2 = "money"

Output: 2

Explanation:
monkeys -> monkey (remove s)
monkey -> money (remove k)

Example 2:

Input: word1 = "neatcdee", word2 = "neetcode"

Output: 3

Explanation:
neatcdee -> neetcdee (replace a with e)
neetcdee -> neetcde (remove last e)
neetcde -> neetcode (insert o)

Constraints:

0 <= word1.length, word2.length <= 100
word1 and word2 consist of lowercase English letters.

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m and n are the lengths of the strings word1 and word2, respectively.

Hint 1

Try to think in terms of recursion and visualize it as a decision tree, as we have choices at each recursion step. Can you determine the recurrence relation and base cases?

Hint 2

We recursively iterate through the strings using indices i and j for word1 and word2, respectively. If the characters at the current indices match, we increment both indices without counting an operation. Otherwise, we have three choices: insert the character at the current index of word1 (increment j), delete the current character of word1 (increment i), or replace the character at index i in word1 (increment both i and j).

Hint 3

If index i goes out of bounds, we return the number of remaining characters in word2 (using insert operations). If index j goes out of bounds, we return the number of remaining characters in word1 (using delete operations). At each step, we return the minimum operation path. This approach is exponential. Can you think of a way to optimize it?

Hint 4

We can use memoization to cache the results and avoid redundant calculations. A hash map or a 2D array can be used to store these results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

This problem asks for the minimum number of operations required to convert word1 into word2.
The allowed operations are:

insert a character
delete a character
replace a character

At any position in both strings, we compare characters at indices i and j.

The recursive function represents:
"What is the minimum number of operations needed to convert word1[i:] into word2[j:]?"

If the characters already match, we simply move forward in both strings without using any operation.
If they do not match, we try all three possible operations and take the minimum cost.

Algorithm

Let m = len(word1) and n = len(word2).
Define a recursive function dfs(i, j):
- i is the current index in word1
- j is the current index in word2
If we reach the end of word1:
- All remaining characters in word2 must be inserted
- Return n - j
If we reach the end of word2:
- All remaining characters in word1 must be deleted
- Return m - i
If word1[i] == word2[j]:
- No operation is needed
- Move both pointers forward: dfs(i + 1, j + 1)
Otherwise, consider all three operations:
- Delete from word1: dfs(i + 1, j)
- Insert into word1: dfs(i, j + 1)
- Replace the character: dfs(i + 1, j + 1)
Take the minimum of these three results and add 1 for the current operation
Start the recursion from (0, 0) and return the final result

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        def dfs(i, j):
            if i == m:
                return n - j
            if j == n:
                return m - i
            if word1[i] == word2[j]:
                return dfs(i + 1, j + 1)
            res = min(dfs(i + 1, j), dfs(i, j + 1))
            res = min(res, dfs(i + 1, j + 1))
            return res + 1

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(3 ^ {m + n})$
Space complexity: $O(m + n)$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

2. Dynamic Programming (Top-Down)

Intuition

This problem asks for the minimum number of edit operations required to convert word1 into word2.
The allowed operations are:

insert a character
delete a character
replace a character

The recursive solution explores all possibilities, but many subproblems repeat. To optimize this, we use top-down dynamic programming (memoization).

A state is uniquely defined by:

i: current index in word1
j: current index in word2

The recursive function answers:
"What is the minimum number of operations needed to convert word1[i:] into word2[j:]?"

By caching results for each (i, j) pair, we avoid recomputing the same states.

Algorithm

Let m = len(word1) and n = len(word2).
Create a memoization map dp where:
- dp[(i, j)] stores the minimum edit distance for word1[i:] and word2[j:]
Define a recursive function dfs(i, j):
- i is the current index in word1
- j is the current index in word2
If i reaches the end of word1:
- Return the number of remaining characters in word2 (n - j)
If j reaches the end of word2:
- Return the number of remaining characters in word1 (m - i)
If the state (i, j) is already in dp:
- Return the cached result
If word1[i] == word2[j]:
- No operation is needed
- Store and return dfs(i + 1, j + 1)
Otherwise, consider all three operations:
- Delete from word1 → dfs(i + 1, j)
- Insert into word1 → dfs(i, j + 1)
- Replace the character → dfs(i + 1, j + 1)
Take the minimum of the three results, add 1, and store it in dp[(i, j)]
Start the recursion from (0, 0) and return the final answer

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        dp = {}
        def dfs(i, j):
            if i == m:
                return n - j
            if j == n:
                return m - i
            if (i, j) in dp:
                return dp[(i, j)]

            if word1[i] == word2[j]:
                dp[(i, j)] = dfs(i + 1, j + 1)
            else:
                res = min(dfs(i + 1, j), dfs(i, j + 1))
                res = min(res, dfs(i + 1, j + 1))
                dp[(i, j)] = res + 1
            return dp[(i, j)]

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

3. Dynamic Programming (Bottom-Up)

Intuition

We want the minimum number of edits needed to convert word1 into word2, where an edit can be:

insert a character
delete a character
replace a character

Instead of using recursion, we can solve this using bottom-up dynamic programming by building the answer for smaller suffixes first.

We define a DP state that answers:
"What is the minimum edit distance between word1[i:] and word2[j:]?"

By filling a table from the end of the strings toward the beginning, every subproblem we need is already solved when we reach it.

Algorithm

Create a 2D DP table dp of size
(len(word1) + 1) × (len(word2) + 1).
Let dp[i][j] represent the minimum number of operations to convert
word1[i:] into word2[j:].
Initialize the base cases:
- If word1 is exhausted (i == len(word1)), all remaining characters of word2 must be inserted:
  - dp[len(word1)][j] = len(word2) - j
- If word2 is exhausted (j == len(word2)), all remaining characters of word1 must be deleted:
  - dp[i][len(word2)] = len(word1) - i
Fill the DP table from bottom-right to top-left:
For each position (i, j):
- If word1[i] == word2[j]:
  - No operation is needed
  - dp[i][j] = dp[i + 1][j + 1]
- Otherwise:
  - Consider all three operations:
    - Delete → dp[i + 1][j]
    - Insert → dp[i][j + 1]
    - Replace → dp[i + 1][j + 1]
  - Take the minimum of these and add 1
After filling the table, the answer is stored in dp[0][0]
Return dp[0][0]

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[float("inf")] * (len(word2) + 1) for i in range(len(word1) + 1)]

        for j in range(len(word2) + 1):
            dp[len(word1)][j] = len(word2) - j
        for i in range(len(word1) + 1):
            dp[i][len(word2)] = len(word1) - i

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

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

4. Dynamic Programming (Space Optimized)

Intuition

We want the minimum number of edits (insert, delete, replace) to convert word1 into word2.

In the 2D DP solution, we used dp[i][j] to represent the answer for word1[i:] and word2[j:].
But notice that each cell dp[i][j] depends only on:

dp[i + 1][j] (delete)
dp[i][j + 1] (insert)
dp[i + 1][j + 1] (replace / match)

So when filling the table from bottom to top, we only need:

the next row (i + 1) and
the current row being built (i)

That means we can optimize space by keeping just two 1D arrays:

dp for the next row
nextDp for the current row

To reduce memory even more, we also ensure the 1D arrays are based on the shorter string (swap if needed).

Algorithm

Let m = len(word1) and n = len(word2).
If word2 is longer than word1, swap them so that n is the smaller length (this keeps the DP arrays small).
Create two arrays of size n + 1:
- dp represents the DP values for row i + 1
- nextDp represents the DP values for row i
Initialize the base case for when word1 is exhausted:
- dp[j] = n - j for all j
- meaning if word1 is empty, we must insert the remaining characters of word2
Iterate i from m - 1 down to 0:
- Set nextDp[n] = m - i
- meaning if word2 is exhausted, we must delete the remaining characters of word1
For each i, iterate j from n - 1 down to 0:
- If word1[i] == word2[j]:
  - no edit needed: nextDp[j] = dp[j + 1]
- Otherwise:
  - take 1 + minimum of:
    - delete: dp[j]
    - insert: nextDp[j + 1]
    - replace: dp[j + 1]
After finishing the row, copy nextDp into dp for the next iteration.
The final answer is dp[0], which represents converting word1[0:] to word2[0:].
Return dp[0]

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if m < n:
            m, n = n, m
            word1, word2 = word2, word1

        dp = [0] * (n + 1)
        nextDp = [0] * (n + 1)

        for j in range(n + 1):
            dp[j] = n - j

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

        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(min(m, n))$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

5. Dynamic Programming (Optimal)

Intuition

We want the minimum number of edits (insert, delete, replace) needed to convert word1 into word2.

The classic DP idea is:

dp[i][j] = minimum operations to convert word1[i:] into word2[j:]

But to compute dp[i][j], we only need three neighboring states:

dp[i + 1][j] (delete from word1)
dp[i][j + 1] (insert into word1)
dp[i + 1][j + 1] (replace, or match if characters are equal)

That means we don't need the full 2D table. We can compress it into a single 1D array dp, and update it row-by-row (from the end of the strings to the start).

The tricky part of in-place updates is that dp[i + 1][j + 1] (the diagonal value) would get overwritten.
So we carry that diagonal value using one extra variable (nextDp), and another temporary variable to shift it correctly while moving left.

We also swap the strings if needed so the DP array is based on the shorter word, keeping memory minimal.

Algorithm

Let m = len(word1) and n = len(word2).
If word2 is longer than word1, swap them so n is the smaller length (smaller DP array).
Create a 1D array dp of size n + 1:
- Initialize it for the base case when word1 is exhausted:
  - dp[j] = n - j (we must insert the remaining characters of word2)
Iterate i from m - 1 down to 0:
- Store the old diagonal value using nextDp (this represents dp[i + 1][j + 1] during updates)
- Update dp[n] = m - i (when word2 is exhausted, we must delete remaining characters of word1)
Iterate j from n - 1 down to 0:
- Save the current dp[j] in temp before overwriting it (this becomes the next diagonal)
- If word1[i] == word2[j]:
  - no operation needed: set dp[j] = nextDp
- Otherwise:
  - take 1 + minimum of:
    - delete: dp[j] (still represents dp[i + 1][j])
    - insert: dp[j + 1] (already updated for current row)
    - replace: nextDp (the diagonal dp[i + 1][j + 1])
- Move the diagonal forward: set nextDp = temp
After finishing all updates, dp[0] represents converting the full word1 into the full word2.
Return dp[0]

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if m < n:
            m, n = n, m
            word1, word2 = word2, word1

        dp = [n - i for i in range(n + 1)]

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

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(min(m, n))$

Where $m$ is the length of $word1$ and $n$ is the length of $word2$ .

Common Pitfalls

Confusing Insert and Delete Operations

When converting word1 to word2, an insert into word1 is equivalent to advancing j (moving forward in word2), while a delete from word1 advances i. Mixing these up leads to incorrect recurrence relations. Remember: insert adds a character to match word2[j], delete removes word1[i].

Incorrect Base Case Initialization

The base cases require returning the number of remaining characters when one string is exhausted. A common mistake is returning 0 or forgetting to handle when i == m (return n - j) or j == n (return m - i). These represent the insertions or deletions needed to complete the transformation.

Forgetting to Add 1 for the Current Operation

When characters don't match, you must add 1 to the minimum of the three recursive calls to account for the current operation. Forgetting this addition results in an answer that's always too small, as it doesn't count the edit being performed at the current position.

Off-by-One Errors in DP Table Dimensions

The DP table needs dimensions (m + 1) x (n + 1) to accommodate the base cases where either string is empty. Using m x n causes index out of bounds errors when accessing dp[m][j] or dp[i][n] for the boundary conditions.

Not Handling Equal Characters Correctly

When word1[i] == word2[j], no operation is needed and you should directly use dp[i+1][j+1] without adding 1. A common mistake is still adding 1 or considering all three operations when characters match, leading to an inflated edit distance.