【LeetCode】动态规划—72. 编辑距离（附完整Python/C++代码）

用户9613193

发布于 2026-06-16 20:02:03

460

动态规划—72. 编辑距离

前言
题目描述
基本思路
- 1. 问题定义
- 2. 理解问题和递推关系
- 3. 解决方法
- - 3.1 动态规划方法
  - 3.2 空间优化的动态规划
- 4. 进一步优化
- 5. 小总结
代码实现
- Python
- - Python3代码实现
  - Python 代码解释
- C++
- - C++代码实现
  - C++ 代码解释
总结:

前言

编辑距离问题是字符串处理中的经典问题之一，广泛应用于拼写纠正、DNA序列比对等领域。通过计算将一个字符串转换为另一个字符串所需的最小操作数，能够帮助我们评估它们之间的相似度。本文将详细分析编辑距离问题的基本思路，提供动态规划的实现方法，并展示 Python 和 C++ 的代码示例。

题目描述

基本思路

1. 问题定义

编辑距离（Edit Distance）是衡量两个字符串之间相似度的一种方法，定义为将一个字符串转换为另一个字符串所需的最少操作次数。允许的操作包括插入字符、删除字符和著换字符。

2. 理解问题和递推关系

设定两个字符串 word1 和 word2，其长度分别为

和

。

定义

dp[i][j]

为将 word1 的前

个字符转换为 word2 的前

个字符所需的最小操作次数。

递推关系：
- 如果
word1[i-1] == word2[j-1]
, 则
d p[i][j]=d p[i-1][j-1]
(不需要任何操作)。
- 如果不相等，考虑三种操作：
  - 插入：
  d p[i][j-1]+1
  - 删除：
  dp [i-1][j]+1
  - 替换：
  dp[\mathrm{i}-1][j-1]+1
综合以上情况，得到：

d p[i][j]=\min (d p[i-1][j]+1, d p[i][j-1]+1, d p[i-1][j-1]+1)

3. 解决方法

3.1 动态规划方法

创建一个二维数组

d p

，其大小为

(m+1) \times(n+1)

，用于存储不同状态的结果。

初始化 dp 数组的边界条件:
d p[i][0]=i
，表示将 word1 的前
i
个字符转换为空字符串的操作次数（全部删除）。
d p[0][j]=j
，表示将空字符串转换为 word2 的前
j
个字符的操作次数（全部插入）。
使用双重循环填充 dp 数组，利用上述递推关系。
最终结果为

d p[m][n]

，即将整个 word1 转换为 word 2 的最小操作次数。

3.2 空间优化的动态规划

由于

d p[i][j]

只依赖于

d p[i-1][j] 、 d p[i][j-1]

和

d p[i-1][j-1]

，可以将空间复杂度优化到

O(n)

，只使用一维数组。

4. 进一步优化

空间复杂度优化：通过使用一维数组来存储当前行的结果，减少内存占用。
时间复杂度：动态规划的时间复杂度为

O(m * n)

，适合中等规模的字符串比较。

5. 小总结

编辑距离问题利用动态规划有效地解决了字符串转换的最优方案。
通过合理的状态设计和空间优化，能够显著提高算法在处理大规模输入时的性能。
理解该问题不仅有助于掌握动态规划的基本思想，还能应用于实际的文本处理和相似度计算等领域。

以上就是问题的基本思路。

代码实现

Python

Python3代码实现

class Solution:
    def minDistance(self, 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(m + 1):
            dp[i][0] = i  # word1 到空字符串的距离
        for j in range(n + 1):
            dp[0][j] = j  # 空字符串到 word2 的距离
        
        # 填充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]

Python 代码解释

初始化：创建 dp 数组并设置边界条件，分别表示将一个字符串转换为空字符串的操作次数。
填充 dp 数组：使用双重循环计算每个子问题的最小操作次数，依赖于之前的结果。
返回结果：最终返回 dp[m][n]，即将整个 word1 转换为 word2 所需的最小操作次数。

C++

C++代码实现

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        // 创建dp数组
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;  // word1 到空字符串的距离
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;  // 空字符串到 word2 的距离
        }
        
        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                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];
    }
};