Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- vector<vector<int>>dp;
- int longestCommonSubsequence(string s1, string s2) {
- int n = s1.size();
- int m = s2.size();
- dp = vector<vector<int>>(n+1 , vector<int>(m+1 , -1));
- for(int i=0;i<=n;i++)
- {
- for(int j=0;j<=m;j++)
- {
- dp[i][j]=-1;
- }
- }
- solve(s1,s2,n,m);
- return dp[n][m];
- }
- int solve(string& s1 , string& s2 ,int n,int m)
- {
- if(n==0 || m==0)return 0;
- if(dp[n][m]!=-1)return dp[n][m];
- if(s1[n-1] == s2[m-1]){
- dp[n][m] = 1 + solve(s1,s2,n-1,m-1);
- }
- else{
- dp[n][m] = max(solve(s1,s2,n-1,m) , solve(s1,s2,n,m-1));
- }
- return dp[n][m];
- }
- };
- class Solution {
- public:
- int longestCommonSubsequence(string s1, string s2) {
- int n = s1.size();
- int m = s2.size();
- int dp[n+1][m+1];
- for(int i=0;i<=n;i++)
- {
- for(int j=0;j<=m;j++)
- {
- dp[i][j]=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] = max({dp[i][j],dp[i-1][j-1]})+1;
- }
- else {
- dp[i][j] = max({dp[i-1][j],dp[i][j-1],dp[i][j]});
- }
- }
- }
- return dp[n][m];
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement