aboutsummaryrefslogtreecommitdiff
path: root/longest_common_subseq.cpp
blob: 56cbaf96d5c92a18a5eb7e8ca5e8759ec51a5f07 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "leetcode.h"

class Solution {
public:
  int longestCommonSubsequence(string text1, string text2) {
    short ans[2][1000] = {};
    for (int i = 0; i < text1.size(); ++i)
      for (int j = 0; j < text2.size(); ++j)
        ans[!(i % 2)][j + 1] = text1[i] == text2[j]
                                   ? ans[i % 2][j] + 1
                                   : max(ans[i % 2][j + 1], ans[!(i % 2)][j]);
    return ans[text1.size() % 2][text2.size()];
  }
};

int main() {
  Solution obj;
  cout << obj.longestCommonSubsequcne("abcde", "ace");       // 3
  cout << endl << obj.longestCommonSubsequcne("abc", "abc"); // 3
}