Leetcode 1143. 最长公共子序列

本文最后更新于:2020年9月20日 晚上

地址:https://leetcode-cn.com/problems/longest-common-subsequence

题目

给定两个字符串 text1text2,返回这两个字符串的最长公共子序列的长度。

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

例如,”ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例 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 <= 1000
  • 1 <= text2.length <= 1000
  • 输入的字符串只含有小写英文字符。

解题思路

这个题并不是我自己做的,是我在学习动态规划的过程中看到的 Leetcode 官方的一篇关于动态规划的文章:算法萌新如何学好动态规划(2),觉得这个题目的解题思路很有意思,所以记录一下~

关于具体的解题思路以及状态转移方程这里不做过多描述了,可以参考原文解题思路。

我觉得很有意思的一个地方是,请看下方代码,按理说我们一般会用一个 n × m 的矩阵用于存储 f[i][j] 的值,即第一个串的前 i 个字符与第二个串的前 j 个字符的最长公共子序列长度,而代码第 5 行却初始化了一个全零的 n+1 × m+1 矩阵,至少我看到这里的时候是有疑惑的,而我最初想到的原因也只是为了理解上更加直观,当然这可以说是一个原因,但事实上这不是最主要的原因。

继续看代码,到第 8 行就明白了,涉及到了对索引 i - 1j - 1 的取值,由于 0 行 0 列根本用不到,而 i 、 j 的初始值均为 1 ,也就是说我们无需再对边界值进行特殊处理,并且将矩阵初始化为全 0 也是有意义的,例如 f[1][1] 就可以直接由 max(f[0][1], f[1][0]) 得到。简言之,对于我们想要得到的这个 n × m 的矩阵,就不需要处理任何的特殊情况了,实在是很方便~

当然上面这些更多的是“取巧”,这个题最核心的部分还是怎么得到它的状态转移方程。

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.length(), m = text2.length();
        vector<vector<int> > f(n+1, vector<int>(m+1, 0));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                f[i][j] = max(f[i-1][j], f[i][j-1]);
                if(text1[i-1] == text2[j-1])
                    f[i][j] = max(f[i][j], f[i-1][j-1]+1);
            }
        }
        return f[n][m];
    }
};

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!