题解 | 编辑距离(一)

1、解题思路

1. 动态规划：定义 dp[i][j] 表示将 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最少操作次数。状态转移方程：如果 str1[i-1] == str2[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[0][j] = j（将空字符串转换为 str2 的前 j 个字符需要 j 次插入操作）。dp[i][0] = i（将 str1 的前 i 个字符转换为空字符串需要 i 次删除操作）。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str1 string字符串
     * @param str2 string字符串
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        int m = str1.size(), n = str2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
                }
            }
        }

        return dp[m][n];
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        m, n = len(str1), len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0:
                    dp[i][j] = j
                elif j == 0:
                    dp[i][j] = i
                elif str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
        return dp[m][n]

3、复杂度分析

1. 动态规划表初始化： dp[i][0] = i（删除操作）。dp[0][j] = j（插入操作）。
2. 状态转移： 字符匹配时，直接继承左上角的值。不匹配时，选择插入、删除或替换中的最小操作数加1。
3. 复杂度分析： 时间复杂度：O(m*n)，填充 m×n 的 dp 表。空间复杂度：O(m*n)，存储 dp 表。

进阶思考

• 如果需要优化空间复杂度，可以将 dp 表优化为一维数组。
• 如果需要输出具体的操作序列，可以在 dp 表中记录操作类型并回溯。