New Problem Solution -"Longest Palindromic Subsequence"

haoel · haoel · commit 2ed675bf7a25 · 2021-03-27T19:53:28.000+08:00
diff --git a/README.md b/README.md
@@ -151,6 +151,7 @@ LeetCode
 |532|[K-diff Pairs in an Array](https://leetcode.com/problems/k-diff-pairs-in-an-array/) | [Python](./algorithms/python/K-diffPairsInAnArray/findPairs.py)|Easy|
 |520|[Detect Capital](https://leetcode.com/problems/detect-capital/) | [C++](./algorithms/cpp/detectCapital/DetectCapital.cpp)|Easy|
 |518|[Coin Change 2](https://leetcode.com/problems/coin-change-2/) | [C++](./algorithms/cpp/coinChange/CoinChange2.cpp)|Medium|
+|516|[Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/) | [C++](./algorithms/cpp/longestPalindromicSubsequence/LongestPalindromicSubsequence.cpp)|Medium|
 |509|[Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) | [C++](./algorithms/cpp/fibonacciNumber/FibonacciNumber.cpp), [Python](./algorithms/python/FibonacciNumber/fib.py)|Easy|
 |497|[Random Point in Non-overlapping Rectangles](https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/) | [C++](./algorithms/cpp/randomPointInNonOverlappingRectangles/randomPointInNonOverlappingRectangles.cpp)|Medium|
 |494|[Target Sum](https://leetcode.com/problems/target-sum/) | [C++](./algorithms/cpp/targetSum/targetSum.cpp)|Medium|
diff --git a/algorithms/cpp/longestPalindromicSubsequence/LongestPalindromicSubsequence.cpp b/algorithms/cpp/longestPalindromicSubsequence/LongestPalindromicSubsequence.cpp
@@ -0,0 +1,90 @@
+// Source : https://leetcode.com/problems/longest-palindromic-subsequence/
+// Author : Hao Chen
+// Date   : 2021-03-27
+
+/***************************************************************************************************** 
+ *
+ * Given a string s, find the longest palindromic subsequence's length in s.
+ * 
+ * A subsequence is a sequence that can be derived from another sequence by deleting some or no 
+ * elements without changing the order of the remaining elements.
+ * 
+ * Example 1:
+ * 
+ * Input: s = "bbbab"
+ * Output: 4
+ * Explanation: One possible longest palindromic subsequence is "bbbb".
+ * 
+ * Example 2:
+ * 
+ * Input: s = "cbbd"
+ * Output: 2
+ * Explanation: One possible longest palindromic subsequence is "bb".
+ * 
+ * Constraints:
+ * 
+ * 	1 <= s.length <= 1000
+ * 	s consists only of lowercase English letters.
+ ******************************************************************************************************/
+
+/*
+
+   supposed s = "abbcba"
+   
+   we can have a matrix, 
+  
+   - dp[start, end] is the longest from s[start] to s[end]
+  
+   - if (start == end) dp[statr, end] = 1, it means every char can be palindromic
+  
+            a b b c b a
+         a  1 0 0 0 0 0  
+         b  0 1 0 0 0 0 
+         b  0 0 1 0 0 0
+         c  0 0 0 1 0 0
+         b  0 0 0 0 1 0
+         a  0 0 0 0 0 1 
+  
+  
+  
+  calculating from the bottom to up. (Note: only care about the top-right trangle)
+  
+            a  b  b  c  b  a
+         a  1  1  2  2  3 [5]  <--  a == a , so "abbcba" comes from "bbcb" + 2 
+         b  0  1 [2] 2  3  3   <--  b == b , so "bb" comes from "" + 2
+         b  0  0  1  1 [3] 3   <--  b == b , so "bcb" comes from "c" + 2 
+         c  0  0  0  1  1 [1]  <--  c != a , so "cba" comes from max("cb", "a") 
+         b  0  0  0  0  1 [1]  <--  b != a , so "ba" comes from max ("b", "a")
+         a  0  0  0  0  0  1 
+         
+  So, we can have the following formular:
+  
+       s[start] != s[end]  ==> dp[start, end] = max (dp[start+1, end], dp[start, end-1]);
+       s[start] == s[end]  ==> dp[start, end] = dp[start+1, end-1] + 2;
+
+*/
+
+
+class Solution {
+public:
+    int longestPalindromeSubseq(string s) {
+        int n = s.size(); 
+        vector<vector<int>> dp(n, vector<int>(n, 0));
+        
+        for (int start = n-1; start>=0; start--) {
+            for (int end = start ; end < n ; end++) {
+                if (start == end) {
+                    dp[start][end] = 1;
+                    continue;
+                }
+                if (s[start] == s[end]) {
+                    dp[start][end] = dp[start+1][end-1] + 2;
+                }else{
+                     dp[start][end] = max (dp[start+1][end], dp[start][end-1]);
+                }
+                
+            }
+        }
+        return dp[0][n-1];
+    }
+};
