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

慈云数据 2024-03-12 技术支持 118 0

代码训练(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,在三种操作下,其最小操作数有下述四种情况:

              1. 已知字符串hors和ros的最小操作数,然后再删除一个字母e,即: MinOperation["hors"]["ros"] + 1。
              2. 已知字符串horse和ro的最小操作数,然后再增加一个字母s,即: MinOperation["horse"]["ro"] + 1。
              3. 已知字符串hors和ro的最小操作数,然后再替换一个字母e -> s,即: MinOperation["hors"]["ro"] + 1。
              4. 已知字符串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值的最小操作数,如下:

              1. 当i = 0时,即MinOperation[0][j] = j,因为word1是空字符串,直接增加j个字符后变成word2。
              2. 当j = 0时,即MinOperation[i][0] = i,因为word2是空字符串,直接删除i个字符后变成word2。
              3. 当i = j = 0时,即MinOperation[0][0] = 0,都是空字符串。

              下面创建一个二维数组 dp,其中 dp[i][j] 表示从 word1 的前 i 个字符转换到 word2 的前 j 个字符所需要的最小操作数。

              1. 初始化边界条件:dp[i][0] 和 dp[0][j] 分别表示将 word1 的前 i 个字符全部删除和将 word2 的前 j 个字符全部插入到 word1。
              2. 遍历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 
                        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] 
微信扫一扫加客服

微信扫一扫加客服

点击启动AI问答
Draggable Icon