解题思路：动态规划

• 定义状态
  设 $dp[i][j]$ 表示 将 word1[0:i] 转换为 word2[0:j] 需要的最少操作数。

• 状态转移方程

  1. 如果 word1[i-1] == word2[j-1]（最后一个字符相同，不需要操作）：

     $$dp[i][j] = dp[i-1][j-1]$$

  2. 如果 word1[i-1] \neq word2[j-1]（最后一个字符不同，需要操作）：
     我们可以进行 插入、删除、替换 三种操作：

     • 插入 word2[j-1]（相当于 word1 长度不变，word2 长度减少）：
       $dp[i][j] = dp[i][j-1] + 1$
     • 删除 word1[i-1]（相当于 word1 长度减少，word2 长度不变）：
       $dp[i][j] = dp[i-1][j] + 1$
     • 替换 word1[i-1] 为 word2[j-1]（相当于 word1 长度减少，word2 长度减少）：
       $dp[i][j] = dp[i-1][j-1] + 1$

     取最小值：

     $$dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 $$

• 初始化

  • dp[i][0] = i（将 word1[0:i] 变为空字符串，需要 i 次删除）
  • dp[0][j] = j（将空字符串变为 word2[0:j]，需要 j 次插入）

• 最终答案
  dp[m][n] 即 word1[0:m] 变为 word2[0:n] 所需的最少操作数。

• 时间复杂度 $O(m \times n)$

• 空间复杂度 $O(m \times n)$

Python 代码

import sys

def min_edit_distance(word1, word2):
    """ 使用动态规划计算编辑距离 """
    m, n = len(word1), len(word2)
    
    # 初始化 DP 数组，dp[i][j] 表示 word1[0:i] 转换为 word2[0:j] 需要的最少操作数
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 处理边界情况
    for i in range(m + 1):
        dp[i][0] = i  # 将 word1[0:i] 转换为空字符串，需要 i 次删除
    for j in range(n + 1):
        dp[0][j] = j  # 将空字符串转换为 word2[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]  # 返回最小编辑距离

def main():
    """ 读取输入并调用求解函数 """
    word1 = sys.stdin.readline().strip()
    word2 = sys.stdin.readline().strip()
    print(min_edit_distance(word1, word2))

if __name__ == "__main__":
    main()

Java 代码

import java.util.*;

public class Main {
    public static int minEditDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        
        // 初始化 DP 数组
        int[][] dp = new int[m + 1][n + 1];

        // 处理边界情况
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // word1[0:i] 变为空字符串，删除 i 次
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // 空字符串变为 word2[0:j]，插入 j 次
        }

        // 填充 DP 表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // 字符相同，不需要操作
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j],    // 删除
                                Math.min(dp[i][j - 1],    // 插入
                                         dp[i - 1][j - 1] // 替换
                                )) + 1;
                }
            }
        }
        return dp[m][n]; // 返回最小编辑距离
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String word1 = sc.next();
        String word2 = sc.next();
        System.out.println(minEditDistance(word1, word2));
        sc.close();
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int minEditDistance(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[0:i] 变为空字符串，删除 i 次
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; // 空字符串变为 word2[0:j]，插入 j 次
    }

    // 填充 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],    // 删除
                                dp[i][j - 1],    // 插入
                                dp[i - 1][j - 1] // 替换
                               }) + 1;
            }
        }
    }
    return dp[m][n]; // 返回最小编辑距离
}

int main() {
    string word1, word2;
    cin >> word1 >> word2;  // 读取两个输入字符串
    cout << minEditDistance(word1, word2) << endl;
    return 0;
}

Leetcode 72.编辑距离-原题链接

题目描述

给定两个单词 word1 和 word2，请返回将 word1 转换为 word2 所需的最少操作数。

允许的操作如下：

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

输入描述

输入包含两行：

• 第一行是字符串 word1（$0 \leq |word1| \leq 500$）。
• 第二行是字符串 word2（$0 \leq |word2| \leq 500$）。

word1 和 word2 仅由小写英文字母组成。

输出描述

输出一行，表示将 word1 转换为 word2 所需的最少操作数。

样例输入 1

horse
ros

样例输出 1

3

说明：

1. horse → rorse （替换 h → r）
2. rorse → rose （删除 r）
3. rose → ros （删除 e）

样例输入 2

intention
execution

样例输出 2

5

说明：

1. intention → inention （删除 t）
2. inention → enention （替换 i → e）
3. enention → exention （替换 n → x）
4. exention → exection （替换 n → c）
5. exection → execution （插入 u）