最长公共子序列
一、题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
例子：
1
2
3
| 输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
|
leetcode：https://leetcode.cn/problems/qJnOS7/
二、思路
这种题目就是典型的动态规划，首先字符串的字符的相对顺序不会变，这也就是说我可以依次取其中一个字符串中 1 个字符、2 个字符、N 个字符做比较。我们申请一个二维数组 dp，这个二维数组的宽和高分别是两个字符串的长度。假设 text1 的长度代表宽，text2 的长度代表高。
比如当我们取 text2 中第一个字符 x 做比较的时候，此时我们填充的就是 dp 的第一行，我们可以遍历 text1，直到遇到和字符 x 相等位置 i，此时让 dp[0][i] = 1，i 后面的也都可以填充为 1。因为这就是一个字符做动态规划时，应该出现的结果。
然后我们再来取 text1 中第一个字符 x 做比较，此时我们填充的就是 dp 的第一列，和填充第一行是同样的逻辑，不再赘述。
那么 dp 二维数组中其他位置应该怎么填呢？比如 dp[i][j] 位置，i 位置就是 text1 的 i 位置，j 位置就是 text2 的 j 位置。主要是看 text1[i] 和 text2[j] 是否相等，如果相等，就说明我这个位置可以填充 dp[i-1][j-1]+1 这个数值，而且还要和 dp[i-1][j] 和 dp[i][j-1] 的数字进行比较。
所以有这样的公式： if text1[i] == text2[j]: dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1) 和 if text1[i] == text2[j]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
dp 的填充解决了，问题也就解决了很大一部分。那么此题求的是最长的公共子序列，那么 dp[M][N] 就是长度。
三、代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <string>
#include <iostream>
#include <vector>
class Solution {
public:
int longestCommonSubsequence(std::string text1, std::string text2) {
if (text1.empty() || text2.empty()) return 0;
std::vector<std::vector<int>> dp(text1.size(), std::vector<int>(text2.size(), 0));
int max_val = 0;
bool flag = false;
for (int i = 0; i < text2.size(); ++i) {
if (flag) {
dp[0][i] = 1;
continue;
}
if (text1[0] == text2[i]) {
dp[0][i] = 1;
flag = true;
max_val = 1;
}
}
flag = false;
for (int i = 0; i < text1.size(); ++i) {
if (flag) {
dp[i][0] = 1;
continue;
}
if (text2[0] == text1[i]) {
dp[i][0] = 1;
flag = true;
max_val = 1;
}
}
for (int i = 1; i < text1.size(); ++i) {
for (int j = 1; j < text2.size(); ++j) {
int val = 0;
if (text1[i] == text2[j]) {
val = dp[i-1][j-1] + 1;
}
dp[i][j] = std::max(val, std::max(dp[i-1][j], dp[i][j-1]));
if (dp[i][j] > max_val) {
max_val = dp[i][j];
}
}
}
return max_val;
}
};
int main() {
Solution s;
std::string str1 = "abcde";
std::string str2 = "ace";
int res = s.longestCommonSubsequence(str1, str2);
std::cout << res << std::endl;
return 0;
}
|
时间复杂度 O(n)，空间复杂度：O(M*N)
四、优雅一点
这道题目可以做的优雅一点。我们的二维数组行和列都增加一。将第一行和第一列的元素处理放在同一个循环中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
if (text1.empty() || text2.empty()) return 0;
unsigned m = text1.size(), n = text2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (unsigned i = 1; i <= m; i++) {
for (unsigned j = 1; j <= n; 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[m][n];
}
};
|
五、空间压缩
和矩阵的最小路径和是一个问题。不过要注意，这里需要保存上一次循环的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
if (text1.empty() || text2.empty()) {
return 0;
}
if (text2.size() < text1.size()) {
std::swap(text1, text2);
}
std::vector<std::pair<int, int>> arr(text1.size()+1, {0, 0});
arr[0] = {0, 0};
for (int i = 1; i < text1.size()+1; i++) {
arr[i] = text1[i-1] == text2[0] ? std::pair<int, int>{0, 1} : std::pair<int, int>{0, 0};
}
for (int i = 1; i < text2.size(); i++) {
arr[0] = {0, 0};
for (int j = 1; j < text1.size()+1; j++) {
arr[j].first = arr[j].second;
arr[j].second = text2[i] == text1[j-1] ? (arr[j-1].first+1) : std::max(arr[j].first, arr[j-1].second);
}
}
return arr[text1.size()].second;
}
};
|