代码训练LeetCode(6)编辑距离

代码训练(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)	字符1`r`	字符2`o`	字符3`s`
(空字符串0)	0	1	2	3
字符1`h`	1
字符2`o`	2
字符3`r`	3
字符4`s`	4
字符5`e`	5

(2) 然后我们可以按照从左到右，从上到下，依次遍历整个表格，直到填满整个表格。

MinOperation	(空字符串0)	字符1`r`	字符2`o`	字符3`s`
(空字符串0)	0	1	2	3
字符1`h`	1	1(替换h)	2	3
字符2`o`	2	2	1(o相等)	2
字符3`r`	3	2	2(删除r)	2
字符4`s`	4	3	3	2(s相等)
字符5`e`	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 <= 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];
}