代码训练(6)LeetCode之编辑距离
Author: Once Day Date: 2024年3月9日
漫漫长路，才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
72. 编辑距离 - 力扣（LeetCode）力扣 (LeetCode) 全球极客挚爱的技术成长平台
文章目录
代码训练(6)LeetCode之编辑距离1. 原题2. 分析3. 代码实现4. 总结
1. 原题
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符删除一个字符替换一个字符
例如对于horse和ros两个单词，其最少操作数为3，即如下三步:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
2. 分析
这种表面一看，似乎是个字符串问题，但是如果按照分类匹配去做，怕是很难得出合理的方法。求两个字符串的编辑距离实际是个动态规划入门题目，动态规划算法是解决这个问题的标准方法。
我们先从逻辑分析一下，对于两个字符串，如horse和ros，在三种操作下，其最小操作数有下述四种情况:
已知字符串hors和ros的最小操作数，然后再删除一个字母e，即: MinOperation["hors"]["ros"] + 1。已知字符串horse和ro的最小操作数，然后再增加一个字母s，即: MinOperation["horse"]["ro"] + 1。已知字符串hors和ro的最小操作数，然后再替换一个字母e -> s，即: MinOperation["hors"]["ro"] + 1。已知字符串hors和ros的最小操作数，如果最后一个字母相同，则不变，即: MinOperation["hors"]["ros"]。
第四种情况为特殊情况，即无需替换，通过上面分类讨论思想，可以发现，MinOperation["horse"]["ros"]取决于其单词前面字符的最小操作，这点很好理解，因为最后一个操作，一定是上述四种操作之一。
我们用i代表horse前i个字符组成的子字符串，j代表ros前j个字符组成的子字符串，则存在下述表达式:
MinOperation[i][j] = Min(
(MinOperation[i-1][j] + 1),
(MinOperation[i][j-1] + 1),
(MinOperation[i-1][j-1] + 1(如果不相等)))
不断递归迭代下去，我们只要确定边界条件，则可按照递推关系求解任意i和j值的最小操作数，如下:
当i = 0时，即MinOperation[0][j] = j，因为word1是空字符串，直接增加j个字符后变成word2。当j = 0时，即MinOperation[i][0] = i，因为word2是空字符串，直接删除i个字符后变成word2。当i = j = 0时，即MinOperation[0][0] = 0，都是空字符串。
下面创建一个二维数组 dp，其中 dp[i][j] 表示从 word1 的前 i 个字符转换到 word2 的前 j 个字符所需要的最小操作数。
初始化边界条件：dp[i][0] 和 dp[0][j] 分别表示将 word1 的前 i 个字符全部删除和将 word2 的前 j 个字符全部插入到 word1。遍历word1和word2的每个字符:
如果当前字符相同，则 dp[i][j] = dp[i-1][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[i][j] 的结果。 最后 dp[length(word1)][length(word2)] 就是我们要找的答案。
按照这个算法我们可以逐步算出不同i和j值的最小操作数，如下表所示:
(1) 首先构建初始化边界条件，即i和j都为0的情况。
MinOperation(空字符串0)字符1r字符2o字符3s(空字符串0)0123字符1h1字符2o2字符3r3字符4s4字符5e5
(2) 然后我们可以按照从左到右，从上到下，依次遍历整个表格，直到填满整个表格。
MinOperation(空字符串0)字符1r字符2o字符3s(空字符串0)0123字符1h11(替换h)23字符2o221(o相等)2字符3r322(删除r)2字符4s4332(s相等)字符5e5443(删除e)
通过上表可以看出来，依次遍历整张表格的流程，也就揭示了操作的流程。
本次问题的性能优化关键点如下:
空间优化：如果我们只关心最终的编辑距离，不需要回溯操作路径，则可以只保留 dp 数组的两行来节省空间。代码优化：确保循环和逻辑判断尽可能简洁，避免不必要的计算。
3. 代码实现
int minDistance(char * word1, char * word2){
int len1 = strlen(word1);
int len2 = strlen(word2);
int dp[len1 + 1][len2 + 1];
if (len1 == 0) {
return len2;
}
if (len2 == 0) {
return len1;
}
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + (dp[i - 1][j - 1] < dp[i][j - 1] ?
(dp[i - 1][j - 1] < dp[i - 1][j] ? dp[i - 1][j - 1] : dp[i - 1][j]) :
(dp[i][j - 1] < dp[i - 1][j]? dp[i][j - 1] : dp[i - 1][j]));
}
}
}
return dp[len1][len2];
}
上面的 C 语言代码实现了编辑距离算法：
minDistance 函数用于计算并返回编辑距离。len1 和 len2 分别是两个输入单词的长度。dp 是一个二维数组，用于存储到当前位置为止的最小编辑距离。初始化 dp 数组的第一行和第一列，这表示一个字符串转换成空字符串所需的步骤数。接下来的双层 for 循环用于填充 dp 数组的剩余部分。我们使用嵌套的三元运算符来找到插入、删除和替换操作中的最小值。函数最后返回 dp[len1][len2]，即将 word1 转换为 word2 所需的最小操作数。
下面是运行结果图(数据仅供参考，不具备实际意义):
4. 总结
本题主要考察了动态规划的理解和应用能力。动态规划是一个非常强大的工具，它可以解决许多看似复杂的问题，将问题分解成一系列子问题，并且保证每个子问题只解决一次，保存其解以避免重复计算。
要提高解决这类问题的能力，我们应该：
理解动态规划的基本概念，如状态转移方程、边界条件等。练习各种不同类型的动态规划问题，从简单到复杂逐渐提升。学会如何将问题分解为子问题，并识别出子问题之间的依赖关系。 的问题，将问题分解成一系列子问题，并且保证每个子问题只解决一次，保存其解以避免重复计算。
Once Day
也信美人终作土，不堪幽梦太匆匆......
如果这篇文章为您带来了帮助或启发，不妨点个赞和关注，再加上一个小小的收藏⭐！
(｡◕‿◕｡)感谢您的阅读与支持~~~
好文链接
您阅读本篇文章共花了：
发表评论