Advertisement
Anwar_Rizk

Longest Common Subsequence

Aug 7th, 2022
746
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     int memo[1005][1005];
  4.     int longestCommonSubsequence(string text1, string text2) {
  5.         memset(memo, -1, sizeof(memo));
  6.         return solve(0, 0, text1, text2);
  7.     }
  8.     int solve(int i, int j, string &s, string &t){
  9.         if(i == s.size() || j == t.size())
  10.             return 0;
  11.         int &ans = memo[i][j];
  12.         if(~ans) return ans;
  13.         if(s[i] == t[j])
  14.             ans = solve(i + 1, j + 1, s, t) + 1;
  15.         else
  16.             ans = max(solve(i + 1, j, s, t), solve(i, j + 1, s, t));
  17.         return ans;
  18.     }
  19. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement