通过率(2/7)
被bp创到了,再也不自己写了。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
int n = s1.size();
int m = s2.size();
if(n==0 || m == 0)
return "-1";
vector<vector<string>> dp(n+1, vector<string> (m+1, ""));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
if(dp[i-1][j] == "") //上面为空
dp[i][j] = dp[i][j-1]; //取左边
else if(dp[i][j-1] == "")
dp[i][j] = dp[i-1][j]; //取上边
else if(s1[i] == s2[j]){
dp[i][j] = dp[i-1][j] + s1[i];
}
else{
if(dp[i-1][j].length() == dp[i][j-1].length())
dp[i][j] = dp[i-1][j]; //取上边
else
dp[i][j] = dp[i][j-1]; //取左边
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
if(dp[n][m] == "")
return "-1";
return dp[n][m];
}
};
class Solution {
public:
string x = "";
string y = "";
string ans(int i, int j, vector<vector<int>> &b){
if(i == 0 || j == 0)
return "";
if(b[i][j] == 1){
return ans(i-1, j-1, b) + x[i-1];
}
else if(b[i][j] == 2)
return ans(i-1, j, b);
else
return ans(i, j-1, b);
}
string LCS(string s1, string s2) {
// write code here
int n = s1.size();
int m = s2.size();
if(n==0 || m == 0)
return "-1";
vector<vector<int>> dp(n+1, vector<int> (m+1));
vector<vector<int>> b(n+1, vector<int> (m+1));
x = s1;
y = s2;
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;
b[i][j] = 1;
}
else{
if(dp[i-1][j] > dp[i][j-1]){
dp[i][j] = dp[i-1][j];
b[i][j] = 2;
}
else{
dp[i][j] = dp[i][j-1];
b[i][j] = 3;
}
}
}
string ANSstr = ans(n,m,b);
cout<<ANSstr;
return ANSstr == "" ? "-1" : ANSstr;
}
};