### 关于LeetCode Problem 72 的 Python 解法 LeetCode 第72题通常被称为 **Edit Distance（编辑距离）**，这是一个经典的动态规划问题。目标是在两个字符串之间找到最小的操作次数来使它们相等，允许的操作包括插入、删除和替换字符。 以下是该问题的一个标准解决方案： #### 动态规划方法 定义 `dp[i][j]` 表示将字符串 `word1[:i]` 转换为 `word2[:j]` 所需的最少操作数。状态转移方程如下： - 如果 `word1[i-1] == word2[j-1]`，则无需额外操作： \[ dp[i][j] = dp[i-1][j-1] \] - 否则，取三种可能操作中的最小值加一： \[ dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 \] 初始条件设置为： - 将空字符串转换为目标字符串所需的操作数等于目标字符串长度； - 反之亦然。 下面是完整的 Python 实现代码： ```python def minDistance(word1: str, word2: str) -> int: m, n = len(word1), len(word2) # 创建 DP 数组并初始化 dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界条件 for i in range(1, m + 1): dp[i][0] = i # 删除所有字符 for j in range(1, n + 1): dp[0][j] = j # 插入所有字符 # 填充 DP 表格 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] = min( dp[i - 1][j], # 删除操作 dp[i][j - 1], # 插入操作 dp[i - 1][j - 1] # 替换操作 ) + 1 return dp[m][n] ``` 上述算法的时间复杂度为 \(O(m \times n)\)，其中 \(m\) 和 \(n\) 是输入字符串的长度[^1]。 #### 进一步优化空间复杂度 由于每次计算仅依赖前一行的结果，可以进一步优化空间复杂度至 \(O(n)\): ```python def minDistance_optimized(word1: str, word2: str) -> int: if len(word1) < len(word2): word1, word2 = word2, word1 # 确保 word1 更长以减少内存占用 previous = list(range(len(word2) + 1)) current = [0] * (len(word2) + 1) for i in range(1, len(word1) + 1): current[0] = i for j in range(1, len(word2) + 1): if word1[i - 1] == word2[j - 1]: current[j] = previous[j - 1] else: current[j] = min(previous[j], current[j - 1], previous[j - 1]) + 1 previous, current = current, previous return previous[-1] ``` 此版本的空间复杂度降低到 \(O(\min(m, n))\)。 ---