通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            jpress从3.x升级到4.x,显示有些问题,慢慢修复中

leetcode 1143最长公共子序列+72编辑距离

100人浏览 / 0人评论 / | 作者:whisper  | 分类: 动态规划  | 标签: 数据结构与算法  | 

作者:whisper

链接:https://www.proprogrammar.com/article/1047

声明:请尊重原作者的劳动,如需转载请注明出处


好久没写算法了,今天学了一下算法视频,重温了一下最长公共子序列和编辑距离,把这两个题放在一起是因为解法很相似,下面就来看一下这两个题目

先看中等的最长公共子序列

1143. 最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace""abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1:

输入:text1 = "abcde", text2 = "ace" 
输出:3  
解释:最长公共子序列是 "ace" ,它的长度为 3 。

示例 2:

输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。

示例 3:

输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。

提示:

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。

JAVA代码如下:

class Solution {
    // LCS 官方题解:https://leetcode-cn.com/problems/longest-common-subsequence/solution/zui-chang-gong-gong-zi-xu-lie-by-leetcod-y7u0/
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

可以看一下上面的官方题解,用动态规划,相信可以看得懂

下面再看一下困难的编辑距离

72. 编辑距离

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1word2 由小写英文字母组成

C++代码如下

class Solution {
public:
// 官方题解:https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
    int minDistance(string word1, string word2) {
        if(word1.size() == 0){
            return word2.size();
        }else if(word2.size() == 0){
            return word1.size();
        }
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        for(int i = 0; i <= word2.size(); i++){
            dp[0][i] = i;
        }
        for(int i = 0; i <= word1.size(); i++){
            dp[i][0] = i;
        }

        for(int i = 1; i <= word1.size(); i++){
            for(int j = 1; j <= word2.size(); j++){
                //dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 1)));
                if(word1[i - 1] == word2[j - 1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    // dp[i-1][j]+1:1增
                    // dp[i][j-1]+1:2增,相当于1删
                    // dp[i-1][j-1]+1:1换
                    dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+1);
                }
            }
        }

        return dp[word1.size()][word2.size()];
    }
};

可以看一下官方题解,也是动态规划,而且与上面的代码很相似,关键部分给出了注释

最后说一下,动态规划即可以由小到大(由局部到整体),也可以由大到小(由整体到局部),此时为了避免重复计算,要用到记忆化的方法(记忆化递归)


亲爱的读者:有时间可以点赞评论一下

点赞(1) 打赏

全部评论

还没有评论!