How to Solve Edit Distance on LeetCode
The Edit Distance problem is a classic dynamic programming challenge, also called Levenshtein Distance.
Problem Statement
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. Allowed operations: insert, delete, replace a character.
Example:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse -> rorse (replace), rorse -> rose (delete), rose -> ros (delete)
Why This Problem Matters for Interviews
- Introduces 2D dynamic programming
- Core for spellcheckers, diff tools, and bioinformatics
- Teaches optimal substructure and overlapping subproblems
Approach to Edit Distance
Dynamic Programming Table (Optimal)
Build a 2D DP table where dp[i][j] is the edit distance between word1[0:i] and word2[0:j].
Time Complexity: O(mn)
Space Complexity: O(mn)
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1):
dp[i][0] = i
for j in range(n+1):
dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+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], # delete
dp[i][j-1], # insert
dp[i-1][j-1], # replace
)
return dp[m][n]
Key Interview Talking Points
- Base cases (empty strings)
- Choices: insert, delete, replace
- Space optimization (rolling arrays)
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DP Table | O(mn) | O(mn) |
Pro Interview Tips
- Draw DP grid for short examples
- Walk through each edit step
- Know 1D optimization for follow-ups