72. Edit Distance
Asked at Apple
Difficulty
Medium
Time
O(n * m)
Space
O(min(n, m))
Pattern
String
Companies
1
Problem
You are given two strings, word1 and word2. Return the minimum number of operations needed to turn word1 into word2.
You may use three operations, each costing 1: insert a character, delete a character, or replace one character with another. You can apply them in any order and at any position.
This is the classic edit distance (Levenshtein distance) problem. The answer is the smallest total cost over all possible sequences of operations.
Turn word1 into word2 with cheap edits
Constraints
- ●
0 <= word1.length, word2.length <= 500 - ●
word1 and word2 consist of lowercase English letters only
Examples
word1 = "horse", word2 = "ros"3word1 = "intention", word2 = "execution"5Asked At
1 companies| 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.
Fill the dp table row by row
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
O(n * m) timeclass 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 runs in O(n * m) time and O(min(n, m)) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.