代码训练(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) 0 1 2 3 字符1h 1 字符2o 2 字符3r 3 字符4s 4 字符5e 5 (2) 然后我们可以按照从左到右,从上到下,依次遍历整个表格,直到填满整个表格。
MinOperation (空字符串0) 字符1r 字符2o 字符3s (空字符串0) 0 1 2 3 字符1h 1 1(替换h) 2 3 字符2o 2 2 1(o相等) 2 字符3r 3 2 2(删除r) 2 字符4s 4 3 3 2(s相等) 字符5e 5 4 4 3(删除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 dp[i][0] = i; } for (int j = 0; j dp[0][j] = j; } for (int i = 1; i for (int j = 1; 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]