LeetCode 72. Edit Distance 题解题目描述给你两个单词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)解题思路方法动态规划思路定义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分别对应删除、插入和替换操作初始化dp[i][0] i将word1的前i个字符删除为空字符串所需的操作数dp[0][j] j将空字符串插入j个字符得到word2的前j个字符所需的操作数复杂度分析时间复杂度O(m × n)其中 m 和 n 是两个单词的长度。需要填充一个 m1 × n1 的表格。空间复杂度O(m × n)需要一个 m1 × n1 的表格来存储状态。代码实现方法动态规划class Solution: def minDistance(self, word1: str, word2: str) - int: m len(word1) n len(word2) # 初始化 dp 表格 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 # 填充 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]测试用例测试用例 1输入word1 horse, word2 ros输出3测试用例 2输入word1 intention, word2 execution输出5测试用例 3输入word1 , word2 a输出1测试用例 4输入word1 a, word2 输出1总结本题是动态规划的经典问题主要考察对状态定义和状态转移方程的理解。通过动态规划我们可以高效地计算出将一个单词转换为另一个单词所需的最少操作数。动态规划的核心思想是通过填充一个二维表格记录将word1的前i个字符转换为word2的前j个字符所需的最少操作数。根据当前字符是否匹配选择不同的操作策略。这种方法不仅适用于编辑距离问题还可以应用于许多其他需要比较两个序列的问题例如最长公共子序列、最长回文子串等。掌握动态规划的思想对于解决这类问题非常重要。