What is the main pattern behind the Edit Distance problem?

The main pattern is state transition dynamic programming, where each subproblem depends on previous states representing partial string conversions.

Can the space complexity be reduced for Edit Distance?

Yes, by storing only the previous DP row, space can be reduced from O(m*n) to O(min(m,n)) without affecting correctness.

How do insertions, deletions, and replacements relate in the DP formula?

They correspond to dp[i-1][j] for deletion, dp[i][j-1] for insertion, and dp[i-1][j-1] for replacement, ensuring each choice is counted correctly.

What are common mistakes in implementing Edit Distance?

Typical mistakes include off-by-one errors, confusing insertion with deletion, and using recursive approaches without memoization.

Is Edit Distance suitable for strings of length 500?

Yes, the DP solution handles up to 500 characters efficiently, especially when optimized for space using only one previous row.

#72

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

编辑距离

给你两个单词 word1 和 word2 ，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符示例 1：输入： word1 = "horse", word2 = "ros" 输出： 3 解释： hors…

字符串动态规划

题目描述

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示将 $word1$ 的前 $i$ 个字符转换成 $word2$ 的前 $j$ 个字符所使用的最少操作数。初始时 $f[i][0] = i$ , $f[0][j] = j$ 。其中 $i \in [1, m], j \in [0, n]$ 。

考虑 $f[i][j]$ ：

如果 $word1[i - 1] = word2[j - 1]$ ，那么我们只需要考虑将 $word1$ 的前 $i - 1$ 个字符转换成 $word2$ 的前 $j - 1$ 个字符所使用的最少操作数，因此 $f[i][j] = f[i - 1][j - 1]$ ；
否则，我们可以考虑插入、删除、替换操作，那么 $f[i][j] = \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1$ 。

综上，我们可以得到状态转移方程：

f[i][j] = \begin{cases} i, & \textit{if } j = 0 \\ j, & \textit{if } i = 0 \\ f[i - 1][j - 1], & \textit{if } word1[i - 1] = word2[j - 1] \\ \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1, & \textit{otherwise} \end{cases}

最后，我们返回 $f[m][n]$ 即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是 $word1$ 和 $word2$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for j in range(1, n + 1):
            f[0][j] = j
        for i, a in enumerate(word1, 1):
            f[i][0] = i
            for j, b in enumerate(word2, 1):
                if a == b:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1
        return f[m][n]

speed

复杂度分析

指标	值
时间	complexity is O(m _n) because each subproblem dp[i][j] is computed once, iterating through all i x j combinations. Space complexity is O(m_ n) for the full DP table, or O(min(m,n)) if optimized to store only one previous row, which is critical for long strings.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks how the DP table represents overlapping subproblems and why it's necessary.
question_mark
Checks if you can optimize space for large input strings up to 500 characters.
question_mark
Inquires about handling equal characters and how it affects the state transition.

warning

常见陷阱

外企场景

error
Failing to initialize base cases correctly, leading to off-by-one errors in dp[0][j] or dp[i][0].
error
Confusing insertion and deletion operations, which can produce incorrect minimal edits.
error
Attempting recursive solutions without memoization, causing exponential time complexity and timeouts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute edit distance with only insertions and deletions allowed, ignoring replacements.
arrow_right_alt
Find all sequences of operations that achieve the minimum edit distance.
arrow_right_alt
Apply edit distance to detect approximate string matching in a text or DNA sequence.

help

常见问题

外企场景

继续练习

#87 扰乱字符串 #91 解码方法 #97 交错字符串