CPP   112
LCS Recursive
Guest on 18th April 2022 02:48:04 AM


  1. class Solution {
  2. public:
  3.     int longestCommonSubsequence(string text1, string text2) {
  4.         int l1 = text1.length();
  5.         int l2 = text2.length();
  6.         if (l1 == 0 || l2 == 0) {
  7.             return 0;
  8.         }
  9.        
  10.         if (l1==1 && l2==1) {
  11.             return text1 == text2;
  12.         }
  13.        
  14.         if (text1[l1-1] == text2[l2-1]) {
  15.             return 1 + longestCommonSubsequence(text1.substr(0,l1-1), text2.substr(0,l2-1));
  16.         } else {
  17.             return max(longestCommonSubsequence(text1, text2.substr(0,l2-1)),longestCommonSubsequence(text1.substr(0,l1-1), text2));
  18.         }
  19.     }
  20. };
Raw Paste

Login or Register to edit or fork this paste. It's free.