【4.3】LeetCode每日一题· 最长公共子序列

2021年04月03日 11时29分

标签： LeetCode 动态规划

## 题目描述
给定两个字符串`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 仅由小写英文字符组成。
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/longest-common-subsequence "题目链接")

## 解题思路
二维dp模版题。详见代码，或[LeetCode官方题解](https://leetcode-cn.com/problems/longest-common-subsequence/solution/zui-chang-gong-gong-zi-xu-lie-by-leetcod-y7u0/)。

时间复杂度$$O(mn)$$，空间复杂度$$O(mn)$$。

**注意：**
1. 如果状态转移方程中`dp[i][j] := text1[0..i], text2[0..j]，且包含i, j`，则需要特判是否边界溢出，溢出时`dp`值为0，这样会导致算法常数较大。因此一般设`dp[i][j]`不包含`text1[i]`和`text2[j]`。
2. 使用`vector`常数较大，一般`dp`使用数组即可。

### 代码
```cpp
class Solution {
public:
    // 求s[0..m], t[0..n]的最长公共子序列的长度
    // dp[i][j] := s[0..i], t[0..j]的最长公共子序列长度(不包含i，j)
    // dp[i][0] = 0; dp[0][j] = 0;
    // dp[i][j] = max(dp[i-1][j], dp[i][j-1]) if s[i-1] != s[j-1]
    // dp[i][j] = dp[i-1][j-1]+1 if s[i-1] == s[j-1]
    int longestCommonSubsequence(string text1, string text2) {
        const int N = text1.length(), M = text2.length();
        int dp[N+1][M+1];
        
        memset(dp, 0, sizeof(dp));
        
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(text1[i-1] == text2[j-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[N][M];
    }
};
```

## 用时和内存
> 执行用时：8 ms，在所有 C++提交中击败了98.97%的用户
> 内存消耗：10.3 MB，在所有 C++提交中击败了92.57%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.3】LeetCode每日一题· 最长公共子序列

所有评论

暂无评论

新增评论