Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/516.html
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.
Algorithm
dp[i][j]
is [i,j]
longest Palindromic Subsequence in range [i,j]
/ dp[i + 1][j - 1] + 2 if (s[i] == s[j])
dp[i][j] =
\ max(dp[i + 1][j], dp[i][j - 1]) if (s[i] != s[j])
Code
-
public class Longest_Palindromic_Subsequence { public class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; --i) { dp[i][i] = 1; for (int j = i + 1; j < n; ++j) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } } }
-
class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i) { dp[i][i] = 1; } for (int j = 1; j < n; ++j) { for (int i = j - 1; i >= 0; --i) { if (s[i] == s[j]) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } };
-
class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): dp[i][i] = 1 # pre-set before inner loop for j in range(i + 1, n): if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2 else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) return dp[0][-1] class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = 1 # cannot move it inside 'for j in range(1, n)' # because below 'for j in range' starting at 1 # so cannot put dp[j][j]=1 inside below for loop for j in range(1, n): for i in range(j - 1, -1, -1): if s[i] == s[j]: dp[i][j] = dp[i + 1][j - 1] + 2 else: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) return dp[0][-1] ############ class Solution(object): def longestPalindromeSubseq(self, s): """ :type s: str :rtype: int """ n = len(s) dp = [1] * n for j in range(1, len(s)): pre = dp[j] for i in reversed(range(0, j)): tmp = dp[i] if s[i] == s[j]: dp[i] = 2 + pre if i + 1 <= j - 1 else 2 else: dp[i] = max(dp[i + 1], dp[i]) pre = tmp return dp[0]
-
func longestPalindromeSubseq(s string) int { n := len(s) dp := make([][]int, n) for i := 0; i < n; i++ { dp[i] = make([]int, n) dp[i][i] = 1 } for j := 1; j < n; j++ { for i := j - 1; i >= 0; i-- { if s[i] == s[j] { dp[i][j] = dp[i+1][j-1] + 2 } else { dp[i][j] = max(dp[i+1][j], dp[i][j-1]) } } } return dp[0][n-1] } func max(a, b int) int { if a > b { return a } return b }