class Solution {
public:
std::string LongestCommonSubsequence(const std::string& s1, const std::string& s2) {
if (s1.empty()||s2.empty()) {
return 0;
}
//dp
std::vector<std::vector<int>> dp(s1.size()+1,std::vector<int>(s2.size()+1,0));
for(int i=1;i<s1.size()+1;i++) {
for(int j=1;j<s2.size()+1;j++) {
dp[i][j]=(s1[i-1]==s2[j-1])?dp[i-1][j-1]+1:std::max(dp[i-1][j],dp[i][j-1]);
}
}
//search path
std::string res;
for(int i=s1.size(),j=s2.size();i>0&&j>0;) {
if(s1[i-1]==s2[j-1]) {
res.insert(0,1,s1[i-1]);
i--;
j--;
}
else {
if(dp[i-1][j]>dp[i][j-1]) {
i--;
}
else {
j--;
}
}
}
return res;
}
};
转载于:https://www.cnblogs.com/smallredness/p/11230235.html
相关资源：JAVA上百实例源码以及开源项目
