The Longest Common Subsequence
- Time : O(nm)
- Space : O(nm)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| vector<int> longestCommonSubsequence(vector<int> a, vector<int> b) {
int dp[111][111] = {};
int n = a.size(), m = b.size();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
dp[i][j] = (a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]));
}
}
int i = n, j = m;
vector<int> res;
while(i and j) {
if(dp[i][j] == dp[i-1][j-1] + 1 and a[i-1] == b[j-1]) {
res.push_back(a[i - 1]);
i--,j--;
} else if(dp[i][j] == dp[i-1][j]) {
i--;
} else j--;
}
reverse(begin(res), end(res));
return res;
}
|
