You are viewing a single comment's thread. Return to all comments →
vector<int> longestCommonSubsequence(vector<int> a, vector<int> b) { vector<int>ans; vector<vector<int>>dp(a.size()+1,vector<int>(b.size()+1)); for(int i=0;i<=a.size();i++) { dp[i][0]=0; } for(int i=0;i<=b.size();i++) { dp[0][i]=0; } for(int i=1;i<=a.size();i++) { for(int j=1;j<=b.size();j++) { if(a[i-1]==b[j-1]) { dp[i][j]=1+dp[i-1][j-1]; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } int i=a.size(),j=b.size(); while(i>0 && j>0) { if(a[i-1]==b[j-1]) { ans.push_back(a[i-1]); i--; j--; } else { if(dp[i-1][j]>dp[i][j-1]) { i--; } else { j--; } } } reverse(ans.begin(),ans.end()); return ans; }
Seems like cookies are disabled on this browser, please enable them to open this website
The Longest Common Subsequence
You are viewing a single comment's thread. Return to all comments →