题目描述：

LeetCode 72题，编辑距离（Edit Distance），是一道经典的动态规划问题。题目要求计算将一个字符串转换为另一个字符串所需的最少编辑操作次数。允许的编辑操作包括：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

题目示例：

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

解题思路：

我们可以使用动态规划（DP）来解决这个问题。定义一个二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少编辑操作次数。

状态转移方程：

1. 当 word1[i-1] == word2[j-1] 时，不需要进行操作，dp[i][j] = dp[i-1][j-1]。
2. 当 word1[i-1] != word2[j-1] 时，需要进行操作，取以下三种操作的最小值：
   • 插入操作：dp[i][j] = dp[i][j-1] + 1
   • 删除操作：dp[i][j] = dp[i-1][j] + 1
   • 替换操作：dp[i][j] = dp[i-1][j-1] + 1

初始化：

• dp[0][j] 表示将空字符串转换为 word2 的前 j 个字符，需要 j 次插入操作。
• dp[i][0] 表示将 word1 的前 i 个字符转换为空字符串，需要 i 次删除操作。

代码实现：

def minDistance(word1, word2): 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

# 填充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] + 1,  # 删除
                           dp[i][j - 1] + 1,  # 插入
                           dp[i - 1][j - 1] + 1)  # 替换

return dp[m][n]

word1 = "horse" word2 = "ros" print(minDistance(word1, word2)) # 输出：3

复杂度分析：

• 时间复杂度： O(m * n)，其中 m 和 n 分别是 word1 和 word2 的长度。
• 空间复杂度： O(m * n)，用于存储 dp 表。

优化空间复杂度：

可以通过滚动数组的方式将空间复杂度优化到 O(min(m, n))，具体实现时只需使用一维数组即可。

总结：

编辑距离问题是一个典型的动态规划问题，通过定义合适的状态和状态转移方程，可以有效地求解。该问题在字符串处理、自然语言处理等领域有广泛的应用。掌握该问题的解法有助于理解和应用动态规划思想。