leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0516.cpp (675B)

      1 class Solution {
      2     int len(const string &s, const int sa, const int sb, vector<vector<int>> &mem) {
      3         if (mem[sa][sb]) return mem[sa][sb];
      4 
      5         int res = 0, a = sa, b = sb;
      6         while (a < b) {
      7             if (s[a] == s[b])
      8                 a++, b--, res += 2;
      9             else {
     10                 res += max(len(s, a + 1, b, mem), len(s, a, b - 1, mem));
     11                 break;
     12             }
     13         }
     14         if (a == b) res++;
     15         mem[sa][sb] = res;
     16         return res;
     17     }
     18 
     19   public:
     20     int longestPalindromeSubseq(string s) {
     21         int n = s.size();
     22         vector<vector<int>> mem(n, vector<int>(n));
     23         return len(s, 0, n - 1, mem);
     24     }
     25 };