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