题解 | #最长公共子序列(二)#记录
最长公共子序列(二)
http://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
int n = s1.size();
int m = s2.size();
vector<vector<int>> dp(n+1,vector<int> (m+1,0));
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(s1[i-1] == s2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
string str;
for(int i = n,j = m;dp[i][j] >= 1;){
if(s1[i-1] == s2[j-1]){
str += s1[i-1];
i--;
j--;
}
else if(dp[i-1][j] >= dp[i][j-1]){
i--;
}
else{
j--;
}
}
reverse(str.begin(), str.end());
return str == "" ? "-1":str;
}
};