31 lines
786 B
C++
31 lines
786 B
C++
#ifndef LONGEST_COMMON_SUBSEQUENCE_H
|
|
#define LONGEST_COMMON_SUBSEQUENCE_H
|
|
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
class Solution {
|
|
public:
|
|
auto longestCommonSubsequence(const string &text1, const string &text2)->int {
|
|
vector<vector<long long>> dp(text1.size() + 1, vector<long long>(text2.size() + 1, 0));
|
|
|
|
long long ans = 0;
|
|
for (int i = 1; i <= text1.size(); i++) {
|
|
for (int j = 1; j <= text2.size(); 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]);
|
|
}
|
|
ans = max(ans, dp[i][j]);
|
|
}
|
|
}
|
|
|
|
return ans;
|
|
}
|
|
};
|
|
|
|
#endif
|