CPP   90

LCS Iterative

Guest on 18th April 2022 03:29:53 AM

  1. class Solution {
  2. public:
  3. int longestCommonSubsequence(string text1, string text2) {
  4.         int l1 = (int) text1.length();
  5.         int l2 = (int) text2.length();
  6.         int f[l1+1][l2+1];
  7.  
  8.         for (int i=0; i<=l1; i++){
  9.             f[i][0] = 0;
  10.         }
  11.         for (int j=0; j<=l2; j++){
  12.             f[0][j] = 0;
  13.         }
  14.         for (int i=1; i<=l1; i++) {
  15.             for (int j = 1; j<=l2; j++) {
  16.                 if (text1[i-1]==text2[j-1]) {
  17.                     f[i][j] = 1 + f[i-1][j-1];
  18.                 } else {
  19.                     f[i][j] = max(f[i-1][j],f[i][j-1]);
  20.                 }
  21.             }
  22.         }
  23.         return f[l1][l2];
  24. }
  25. };

Raw Paste


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