aboutsummaryrefslogtreecommitdiff
path: root/other/longest_palindromic_subseq.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/longest_palindromic_subseq.cpp')
-rw-r--r--other/longest_palindromic_subseq.cpp35
1 files changed, 0 insertions, 35 deletions
diff --git a/other/longest_palindromic_subseq.cpp b/other/longest_palindromic_subseq.cpp
deleted file mode 100644
index f2a074f..0000000
--- a/other/longest_palindromic_subseq.cpp
+++ /dev/null
@@ -1,35 +0,0 @@
-// 516. Longest Palindromic Subsequence
-#include "leetcode.h"
-
-/*
- * given string 's', find the longest palindromic susbsequences
- * of length in 's'. a subsequcnes is a sequence that can be derived
- * from another sequence by deleting some or no elements without
- * changing the order of the remaining elements
- */
-
-class Solution {
-public:
- int longestPalindromeSubseq(string s) {
- int n = s.size();
- vector<int> dp(n, 0);
- for (int i = n - 1; i >= 0; i--) {
- vector<int> new_dp(n, 0);
- new_dp[i] = 1;
- for (int j = i + 1; j < n; j++) {
- if (s[i] == s[j])
- new_dp[j] = 2 + dp[j - 1];
- else
- new_dp[j] = max(dp[j], new_dp[j - 1]);
- }
- dp = new_dp;
- }
- return dp[n - 1];
- }
-};
-
-int main() {
- Solution obj;
- printf("%d\n", obj.longestPalindromeSubseq("bbbab")); // expect: 4
- printf("%d\n", obj.longestPalindromeSubseq("cbbd")); // expect: 2
-}