⚡Flashcard Drill➔
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

  1. dp[i][j] is the edit distance between word1[0..i-1] and word2[0..j-1].
  2. If the last characters match, no operation is needed, so dp[i][j] = dp[i-1][j-1].
  3. 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.
  4. The base cases are dp[i][0] = i (delete everything) and dp[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 of word2 (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..m and the first row runs 0..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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems