NeetCode #733LC-72Medium2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems#733 · #72 · Edit Distance(编辑距离)
📌 Problem Statement & Constraints
Given strings
word1 and word2, return the minimum number of insertions, deletions, or replacements needed to convert word1 into word2. Constraints: 0 <= word1.length, word2.length <= 500, lowercase English letters.💡 Core Algorithmic Approaches
dp[i][j]is the edit distance betweenword1[0..i-1]andword2[0..j-1].- If the last characters match, no operation is needed, so
dp[i][j] = dp[i-1][j-1]. - Otherwise take the cheapest of replace (
dp[i-1][j-1]), delete (dp[i-1][j]), and insert (dp[i][j-1]), then add one. - The base cases are
dp[i][0] = i(delete everything) anddp[0][j] = j(insert everything).
💻 Benchmark Python3 Implementation
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
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 - 1], # replace
dp[i - 1][j], # delete
dp[i][j - 1]) # insert
return dp[m][n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): one state per pair of prefixes.
💾 Space Complexity
O(m * n), reducible to O(n).
⚠️ Interview Pitfalls & Follow-ups
- Mismatching operations and neighbours: delete consumes a character of
word1(dp[i-1][j]), insert consumes one ofword2(dp[i][j-1]), and replace consumes both (dp[i-1][j-1]). - Adding 1 on a match: when the characters match, the cost is copied with no extra operation.
- Wrong base cases: the first column runs
0..mand the first row runs0..n. - Assuming transposition is allowed: only three operations exist, so this is not Damerau-Levenshtein.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.