#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * longest common subsequence * @param s1 string字符串 the string * @param s2 string字符串 the string * @return string字符串 */ string Str1=""; string Str2=""; string dfs(int i,int j,vector<vector<int>> &b){ string ans=""; if (i==0||j==0) return ans; if(b[i][j]==1){ ans += dfs(i-1,j-1,b); ans += Str1[i-1]; }else if(b[i][j]==2){ ans += dfs(i-1,j,b); }else{ ans += dfs(i,j-1,b); } return ans; } string LCS(string s1, string s2) { // write code here if(s1.empty() || s2.empty()) return "-1"; int x=s1.size(); int y=s2.size(); Str1 = s1; Str2 = s2; vector<vector<int>> dp(x+1,vector<int>(y+1,0));//记录s1以i为结束,s2以j为结束的最长公共子序列 vector<vector<int>> b(x+1,vector<int>(y+1,0)); for(int i=1;i<=x;i++) for(int j=1;j<=y;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 res = dfs(x,y,b); return res ==""?"-1":res; } };