leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0516.cpp (675B)

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