commit eab73660e5f82bd021bac7afac5287c62827e0ec
parent 36a8c18aae0bbe94a596dff3d8d42eb0c31d8cb8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 6 Feb 2023 16:30:11 +0100
Dynamic Programming I: Day 17
Diffstat:
3 files changed, 48 insertions(+), 0 deletions(-)
diff --git a/Problems/0005.cpp b/Problems/0005.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ const string len(const string &s, int a, int b) {
+ while (a >= 0 && b < s.size() && s[a] == s[b]) a--, b++;
+ return s.substr(a + 1, b - a - 1);
+ }
+
+public:
+ string longestPalindrome(string s) {
+ string res = "", t;
+ s.push_back(' ');
+ for (int i = 0; i < s.size(); i++) {
+ t = len(s, i, i);
+ if (t.size() > res.size()) res = t;
+ if (s[i] != s[i + 1]) continue;
+ t = len(s, i, i + 1);
+ if (t.size() > res.size()) res = t;
+ }
+ return res;
+ }
+};
diff --git a/Problems/0516.cpp b/Problems/0516.cpp
@@ -0,0 +1,26 @@
+class Solution {
+ int len(const string &s, const int sa, const int sb,
+ vector<vector<int>> &mem) {
+ if (mem[sa][sb]) return mem[sa][sb];
+
+ int res = 0, a = sa, b = sb;
+ while (a < b) {
+ if (s[a] == s[b])
+ a++, b--, res += 2;
+ else {
+ res += max(len(s, a + 1, b, mem), len(s, a, b - 1, mem));
+ break;
+ }
+ }
+ if (a == b) res++;
+ mem[sa][sb] = res;
+ return res;
+ }
+
+public:
+ int longestPalindromeSubseq(string s) {
+ int n = s.size();
+ vector<vector<int>> mem(n, vector<int>(n));
+ return len(s, 0, n - 1, mem);
+ }
+};
diff --git a/README.md b/README.md
@@ -26,6 +26,7 @@ for solving problems.
| 0001 | Easy | [Two Sum](Problems/0001.cpp) |
| 0002 | Medium | [Add Two Numbers](Problems/0002.cpp) |
| 0003 | Medium | [Longest Substring Without Repeating Characters](Problems/0003.cpp) |
+| 0005 | Medium | [Longest Palindromic Substring](Problems/0005.cpp) |
| 0006 | Medium | [Zigzag Conversion](Problems/0006.cpp) |
| 0011 | Medium | [Container With Most Water](Problems/0011.cpp) |
| 0012 | Medium | [Integer to Roman](Problems/0012.cpp) |
@@ -212,6 +213,7 @@ for solving problems.
| 0501 | Easy | [Find Mode in Binary Search Tree](Problems/0501.cpp) |
| 0503 | Medium | [Next Greater Element II](Problems/0503.cpp) |
| 0509 | Easy | [Fibonacci Number](Problems/0509.cpp) |
+| 0516 | Medium | [Longest Palindromic Subsequence](Problems/0516.cpp) |
| 0520 | Easy | [Detect Capital](Problems/0520.cpp) |
| 0530 | Easy | [Minimum Absolute Difference in BST](Problems/0530.cpp) |
| 0538 | Medium | [Convert BST to Greater Tree](Problems/0538.cpp) |
