当前位置：
首页 >
算法：编辑距离
发布时间：2025/6/15
47
豆豆
题目描述：
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
代码：
class Solution { public:int minDistance(string word1, string word2) {int n = word1.length();int m = word2.length();// 有一个字符串为空串if (n * m == 0) return n + m;// DP 数组int D[n + 1][m + 1];// 边界状态初始化for (int i = 0; i < n + 1; i++) {D[i][0] = i;}for (int j = 0; j < m + 1; j++) {D[0][j] = j;}// 计算所有 DP 值for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {int left = D[i - 1][j] + 1;int down = D[i][j - 1] + 1;int left_down = D[i - 1][j - 1];//判断两个字符串最后一个字符是否相等if (word1[i - 1] != word2[j - 1]) left_down += 1;D[i][j] = min(left, min(down, left_down));}}return D[n][m];} };这是一道很经典的动态规划题目，大家可以去学学，我起抛砖引玉的作用。
详细学习地址：https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
总结
