Skip to content

Latest commit

 

History

History
207 lines (131 loc) · 8.18 KB

为了绝杀编辑距离,卡尔做了三步铺垫.md

File metadata and controls

207 lines (131 loc) · 8.18 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

动态规划之编辑距离总结篇

本周我们讲了动态规划之终极绝杀:编辑距离,为什么叫做终极绝杀呢?

细心的录友应该知道,我们在前三篇动态规划的文章就一直为 编辑距离 这道题目做铺垫。

判断子序列

动态规划:392.判断子序列 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

这道题目 其实是可以用双指针或者贪心的的,但是我在开篇的时候就说了这是编辑距离的入门题目,因为从题意中我们也可以发现,只需要计算删除的情况,不用考虑增加和替换的情况。

  • if (s[i - 1] == t[j - 1])
    • t中找到了一个字符在s中也出现了
  • if (s[i - 1] != t[j - 1])
    • 相当于t要删除元素,继续匹配

状态转移方程:

if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];

不同的子序列

动态规划:115.不同的子序列 给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。

本题虽然也只有删除操作,不用考虑替换增加之类的,但相对于动态规划:392.判断子序列就有难度了,这道题目双指针法可就做不了。

当s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。

一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。

这里可能有同学不明白了,为什么还要考虑 不用s[i - 1]来匹配,都相同了指定要匹配啊。

例如: s:bagg 和 t:bag ,s[3] 和 t[2]是相同的,但是字符串s也可以不用s[3]来匹配,即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配,即:s[0]s[1]s[3]组成的bag。

所以当s[i - 1] 与 t[j - 1]相等时,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

当s[i - 1] 与 t[j - 1]不相等时,dp[i][j]只有一部分组成,不用s[i - 1]来匹配,即:dp[i - 1][j]

所以递推公式为:dp[i][j] = dp[i - 1][j];

状态转移方程:

if (s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
    dp[i][j] = dp[i - 1][j];
}

两个字符串的删除操作

动态规划:583.两个字符串的删除操作给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。

本题和动态规划:115.不同的子序列相比,其实就是两个字符串可以都可以删除了,情况虽说复杂一些,但整体思路是不变的。

  • 当word1[i - 1] 与 word2[j - 1]相同的时候
  • 当word1[i - 1] 与 word2[j - 1]不相同的时候

当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况:

情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1

情况二:删word2[j - 1],最少操作次数为dp[i][j - 1] + 1

情况三:同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值,所以当word1[i - 1] 与 word2[j - 1]不相同的时候,递推公式:dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

状态转移方程:

if (word1[i - 1] == word2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1];
} else {
    dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
}

编辑距离

动态规划:72.编辑距离 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

编辑距离终于来了,有了前面三道题目的铺垫,应该有思路了,本题是两个字符串可以增删改,比 动态规划:判断子序列动态规划:不同的子序列动态规划:两个字符串的删除操作都要复杂的多。

在确定递推公式的时候,首先要考虑清楚编辑的几种操作,整理如下:

  • if (word1[i - 1] == word2[j - 1])
    • 不操作
  • if (word1[i - 1] != word2[j - 1])

也就是如上四种情况。

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑,dp[i][j] 就应该是 dp[i - 1][j - 1],即dp[i][j] = dp[i - 1][j - 1];

此时可能有同学有点不明白,为啥要即dp[i][j] = dp[i - 1][j - 1]呢?

那么就在回顾上面讲过的dp[i][j]的定义,word1[i - 1] 与 word2[j - 1]相等了,那么就不用编辑了,以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1] 就是 dp[i][j]了。

在下面的讲解中,如果哪里看不懂,就回想一下dp[i][j]的定义,就明白了。

在整个动规的过程中,最为关键就是正确理解dp[i][j]的定义!

if (word1[i - 1] != word2[j - 1]),此时就需要编辑了,如何编辑呢?

操作一:word1增加一个元素,使其word1[i - 1]与word2[j - 1]相同,那么就是以下标i-2为结尾的word1 与 i-1为结尾的word2的最近编辑距离 加上一个增加元素的操作。

即 dp[i][j] = dp[i - 1][j] + 1;

操作二:word2添加一个元素,使其word1[i - 1]与word2[j - 1]相同,那么就是以下标i-1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个增加元素的操作。

即 dp[i][j] = dp[i][j - 1] + 1;

这里有同学发现了,怎么都是添加元素,删除元素去哪了。

word2添加一个元素,相当于word1删除一个元素,例如 word1 = "ad" ,word2 = "a",word2添加一个元素d,也就是相当于word1删除一个元素d,操作数是一样!

操作三:替换元素,word1替换word1[i - 1],使其与word2[j - 1]相同,此时不用增加元素,那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。

即 dp[i][j] = dp[i - 1][j - 1] + 1;

综上,当 if (word1[i - 1] != word2[j - 1]) 时取最小的,即:dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

递归公式代码如下:

if (word1[i - 1] == word2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1];
}
else {
    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}

总结

心思的录友应该会发现我用了三道题做铺垫,才最后引出了动态规划:72.编辑距离 ,Carl的良苦用心呀,你们体会到了嘛!

其他语言版本

Java:

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            dp[i][0] = i;
        }
        for(int i = 1; i <= n; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                int left = dp[i][j-1]+1;
                int mid = dp[i-1][j-1];
                int right = dp[i-1][j]+1;
                if(word1.charAt(i-1) != word2.charAt(j-1)){
                    mid ++;
                }
                dp[i][j] = Math.min(left,Math.min(mid,right));
            }
        }
        return dp[m][n];
    }
}

Python:

Go: