Framework Thinking - Neetcode 150 - Edit Distance

Here is solutions for Edit Distance.

1. Understand the problem

You are given two strings word1 and word2.
You can perform three operations on word1:
1. Insert a character
2. Delete a character
3. Replace a character
Each operation costs 1 step.
👉 Your task: Find the minimum number of operations needed to convert word1 into word2.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

Are strings empty allowed?

✅ Yes. Either or both can be empty.

What happens if one string is empty?

✅ Answer = length of the other string (all inserts or deletes).

Are operations weighted equally?

✅ Yes, insert/delete/replace all cost 1.

Character set?

✅ Lowercase English letters (but DP works for any charset).

Max length of strings?

✅ Typically up to 500 – 1000 → O(n·m) DP is required.

Edge cases:

”” , “” → 0
“abc”, “” → 3
“a”, “a” → 0
“a”, “b” → 1

3. Explore examples.

Example 1

word1 = "horse"
word2 = "ros"

Possible operations:

horse → rorse (replace h → r)
rorse → rose  (delete r)
rose  → ros   (delete e)

output = 3

Example 2:

word1 = "intention"
word2 = "execution"

output = 5

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1: Pure Recursion (Naive – Exponential) - Time O(3^(N + M)), Space O(N + M)

Let f(i, j) = edit distance between:
- word1[i:]
- word2[j:]

If word1[i] == word2[j]:
    f(i, j) = f(i+1, j+1)
Else:
    f(i, j) = 1 + min(
        f(i, j+1),    # insert
        f(i+1, j),    # delete
        f(i+1, j+1)   # replace
    )

Time: O(3^(N + M)).
Space: O(N + M)

4.2. Solution 2: Top-Down DP (Memoization) - Time O(N * M), Space O(N * M)

State
- dp[i][j] = min operations to convert word1[i:] → word2[j:]
Time: O(N * M)
Space: O(N * M)

4.3. Solution 3: Bottom-Up DP (Most Preferred)

State:
- dp[i][j] = min operations to convert: word1[0:i] → word2[0:j]

dp[0][j] = j   # insert j chars
dp[i][0] = i   # delete i chars

# Ensure we need to change it, but come from each of 3 cases.
dp[i][j] = 1 + min(
    dp[i][j-1],    # insert
    dp[i-1][j],    # delete
    dp[i-1][j-1]   # replace
)

Time: O(N * M)
Space: O(N * M)

5. Implement solutions.

5.1. Recursion - Time O(3^(N + M)), Space O(N + M)

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 = 1 + min(dfs(i + 1, j), dfs(i, j + 1) , dfs(i + 1, j + 1))
            return res

        return dfs(0, 0)

Time: O(3^(N + M))
Space: O(N + M)

5.2. Dynamic Programming (Top-Down) - Time O(M * N), Space O(M * N)

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: O(M * N)
Space: O(M * N)

5.3. Bottom-Up DP - Time O(M * N), Space O(M * N)

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

        dp = [[0] * (m + 1) for _ in range(n + 1)]

        # Base cases
        for i in range(n + 1):
            # Convert word[:i] to empty string
            dp[i][0] = i
        for j in range(m + 1):
            # Convert empty string to word[:j]
            dp[0][j] = j

        # Fill table
        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][j - 1],    # insert
                        dp[i - 1][j],    # delete
                        dp[i - 1][j - 1] # replace
                    )

        return dp[n][m]

Time: O(M * N)
Space: O(M * N)

5.4. Optimize Space - Time O(M * N), Space O(M)

So instead of storing the whole table:

prev = previous DP row → dp[i-1][*]
curr = current DP row → dp[i][*]

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

        # Note: prev[j] = dp[i-1][j]
        prev = list(range(m + 1))

        for i in range(1, n + 1):
            # dp[i][0], dp[i][1],...,dp[i][m]
            curr = [i] + [0] * m
            for j in range(1, m + 1):
                if word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1]
                else:
                    curr[j] = 1 + min(
                        curr[j - 1],  # insert
                        prev[j],      # delete
                        prev[j - 1]   # replace
                    )
            prev = curr

        return prev[m]

Time: O(M * N)
Space: O(M)

6. Dry run testcases.

Optimize from 2D array to 1D array => Just a way to optimize space.

December 7, 2025