【LeetCode75】第六十四题 最长公共子序列

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

 

分析：

给我们两个字符串，问我们最长公共子串的最长长度是多少。

那么我首先想到就是LeetCode75的第十一题判断子序列，题目也是给两个字符串，不过是问一个字符串是不是另一个字符串的子序列。

我们本题暴力的一个解法也可以参考那题，我们将较短的一个字符串的每个字符当作不同子序列的起点，去看看这些不同的子序列能匹配另一个字符串的多少字符，返回符合要求的最长子序列的长度即可。

当然还可以使用动态规划来做。

我们首先需要先找到一个递推的方法，能不能把字符串拆成更短的字符串来求出最长公共子序列的长度，再根据较短的字符串来推出较长的字符串的结果，最终推断出完整字符串的最长公共子序列呢。

答案是可以的。

他们按照顺序每有一对一致的字符，那么就是在这对字符出现之前的最长公共子序列长度+1。

而这对字符出现之前的最长公共子序列又是又按照顺序出现的字符一致的对数决定的。

那么我们就可以列出一个二维dp数组，dp[ i ][ j ] 可以表示为当字符串1的长度为 i 且字符串2的长度为 j 时，两个字符串的最长公共子序列的长度。

如果字符串1的第 i 个字符和字符串2的第 j 个字符一致，那么就是说当字符串1的长度等于 i 和字符串2的长度等于 j 时的最长公共子序列的长度等于 当字符串1的长度等于 i - 1 和字符串2的长度等于 j -1 时的最长公共子序列的长度+1。

那如果字符串1的第 i 个字符和字符串2的第 j 个字符不一致呢。那么他们此时的最长公共子序列的长度就等于字符串1的长度等于 i - 1 且字符串2的长度等于 j 时和字符串1的长度等于 i 且字符串2的长度等于 j - 1 时的最长公共子序列。

至此，我们就找出了递推公式。

那最后的问题就是初始化。

首先我们的递推公式里有-1这个操作，那么我们的 i 和 j 都需要从1开始遍历才不至于在 -1 的时候越界。所以我们需要的是初始化 i = 0 和 j = 0的位置。

那么我们再思考一下dp数组的含义是什么。那可不就是dp[ i ][ j ]就是字符串1的长度为 i 且 字符串2的长度为 j 的时候它们俩最长公共子序列的长度嘛。

那不管是 i = 0还是 j = 0，因为俩字符串至少是有一个字符串是空字符串，所以最长公共子序列自然就是0。所以我们直接把dp数组全部初始化成0就行。

最后返回dp数组的最后一个元素就行。

代码：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vectorint>>dp(text1.size()+1,vector<int>(text2.size()+1,0));
        for(int i=1;isize()+1;i++){
            for(int j=1;jsize()+1;j++){
                if(text1[i-1]==text2[j-1]){ //如果字符相同,那么最长公共子序列的长度加1
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);    //不相同,那就继承之前的最长公共子序列长度
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};