dp O(mn) time O(mn) space
LCS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length(), n = text2.length();
vector<vector<int>> f(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}
return f[m][n];
}
};
|
O(mn) time O(n) space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length(), n = text2.length();
vector<vector<int>> f(2, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int k = i & 1, j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
f[k][j] = f[k ^ 1][j - 1] + 1;
} else {
f[k][j] = max(f[k ^ 1][j], f[k][j - 1]);
}
}
}
return f[m & 1][n];
}
};
|