Edit Distance
Asked at Apple
Problem
Given two words, find the minimum number of operations (insert, delete, replace) required to convert one word into the other.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
How to Think About It
Brute force: try all sequences of operations recursively. Branching factor is 3 per character, giving O(3^(n+m)) time in the worst case.
Define dp[i][j] as the edit distance between word1[0..i-1] and word2[0..j-1]. Base cases: dp[0][j] = j (insert all), dp[i][0] = i (delete all).
Recurrence: if word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1] (no operation needed). Otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) for delete, insert, replace.
Space can be optimized to O(min(n,m)) by using two rows (previous and current) since each cell only depends on the row above.
The three operations map to: delete = dp[i-1][j] + 1, insert = dp[i][j-1] + 1, replace = dp[i-1][j-1] + 1.
Example: word1 = "horse", word2 = "ros". dp table:
[0,1,2,3]
[1,1,2,3]
[2,1,1,2]
[3,2,1,2]
[4,3,2,2]
[5,4,3,3]
Answer is 3: horse -> rorse (replace h->r), rorse -> rose (delete r), rose -> ros (delete e).
Optimal Approach
Step 1: Create a 2D dp table of size (n+1) x (m+1) where n = len(word1), m = len(word2).
Step 2: Initialize base cases: dp[i][0] = i for all i (delete all characters from word1), dp[0][j] = j for all j (insert all characters of word2).
Step 3: Fill the table row by row. For each i from 1 to n and j from 1 to m:
- 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], dp[i][j-1], dp[i-1][j-1])
Step 4: Return dp[n][m].
Step 5: Example walkthrough with word1 = "intention", word2 = "execution":
The DP table is filled row by row. Key cells: dp[1][1] = 1 (i->e replace), dp[2][2] = 1 (n->x replace), ... dp[9][9] = 5.
5 operations: replace i->e, replace n->x, insert c, replace t->u, delete i.
Time: O(n * m). Space: O(n * m), reducible to O(min(n, m)) with two-row optimization.
What Trips People Up in Real Interviews
Confusing insert and delete costs. Deleting from word1 costs 1 and uses dp[i-1][j]. Inserting into word1 costs 1 and uses dp[i][j-1].
Forgetting that a matching character still requires looking at dp[i-1][j-1], not skipping the cell entirely.
Not handling base cases correctly. dp[0][j] = j means converting empty string to j-character string requires j inserts.
Trying to use a greedy approach (always do the cheapest operation at each step). Greedy does not work here because a replace now might save operations later.
Using a 1D array naively without understanding the dependency order. Each cell depends on three neighbors, so you need two rows or careful ordering.
Solution Code
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)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
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], dp[i][j - 1], dp[i - 1][j - 1])
return dp[n][m]Frequently Asked Questions
What is the Edit Distance problem?
Given two words, find the minimum number of operations (insert, delete, replace) required to convert one word into the other.
How do you solve Edit Distance?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Edit Distance?
Edit Distance is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Edit Distance?
- Confusing insert and delete costs. Deleting from word1 costs 1 and uses `dp[i-1][j]`. Inserting into word1 costs 1 and uses `dp[i][j-1]`.
- Forgetting that a matching character still requires looking at `dp[i-1][j-1]`, not skipping the cell entirely.
- Not handling base cases correctly. `dp[0][j] = j` means converting empty string to j-character string requires j inserts.
- Trying to use a greedy approach (always do the cheapest operation at each step). Greedy does not work here because a replace now might save operations later.
- Using a 1D array naively without understanding the dependency order. Each cell depends on three neighbors, so you need two rows or careful ordering.