Advertisement
Kali_prasad

length of LCS using recursion

Jun 19th, 2022
25
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     int LCS(vector<vector<int>> &dp,string s1,string s2,int m,int n)
  4.     {
  5.         if(dp[m][n]!=-1) return dp[m][n];
  6.         if(n==0||m==0) return dp[m][n]=0;
  7.         if(s1[m-1]==s2[n-1])
  8.             return dp[m][n]=1+LCS(dp,s1,s2,m-1,n-1);
  9.         else
  10.             return dp[m][n]=max(LCS(dp,s1,s2,m-1,n),LCS(dp,s1,s2,m,n-1));
  11.     }
  12.     int longestCommonSubsequence(string t1, string t2) {
  13.         int m=t1.length(),n=t2.length();
  14.         vector<vector<int>> dp(m+1,vector<int>(n+1,-1));
  15.         return LCS(dp,t1,t2,m,n);
  16.     }
  17. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement