当前位置：首页 > news >正文

LeetCode 72. 编辑距离（Edit Distance）| 动态规划详解

news 2025/6/13 13:05:51

72. 编辑距离

📘 题目描述

给你两个单词 word1 和 word2，请计算将 word1 转换为 word2 所需的最少操作数。

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

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

✅ 示例

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

🔍 解题思路：动态规划（DP）

✅ 状态定义

dp[i][j] 表示将 word1[0:i] 转换为 word2[0:j] 的最小操作数。

✅ 状态转移方程

如果 word1[i - 1] == word2[j - 1]，当前字符相等，不需要额外操作：
```
dp[i][j] = dp[i - 1][j - 1]
```
否则，取三种操作的最小值：

dp[i][j] = min(dp[i - 1][j] + 1,     # 删除 word1[i - 1]dp[i][j - 1] + 1,     # 插入 word2[j - 1]dp[i - 1][j - 1] + 1  # 替换 word1[i - 1] 为 word2[j - 1]
)

✅ 边界初始化

dp[0][j] = j：将空字符串变成 word2 的前 j 个字符，需插入 j 次。
dp[i][0] = i：将 word1 的前 i 个字符变为空字符串，需删除 i 次。

💻 Python代码实现

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] = ifor 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] = min(dp[i - 1][j] + 1,     # 删除dp[i][j - 1] + 1,     # 插入dp[i - 1][j - 1] + 1  # 替换)return dp[m][n]