Description
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.
Solution
This is very similar to the problem Longest Common Subsequence if you look very closely.
Basically we are searching for the longest common subseqnence of string s and the reversed string s.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int longestPalindromeSubseq(string s) {
size_t n = s.size() + 1;
vector<vector<int>> dp(n, vector<int>(n));
for (size_t i = 1; i < n; i++) {
for (size_t j = 1; j < n; j++) {
if (s[i-1] == s[s.size()-j])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp.back().back();
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
impl Solution {
pub fn longest_palindrome_subseq(s: String) -> i32 {
let n = s.len()+1;
let mut dp: Vec<Vec<i32>> = vec![vec![0; n]; n];
for (i, c1) in s.chars().enumerate() {
for (j, c2) in s.chars().rev().enumerate() {
dp[i+1][j+1] = if (c1 == c2) {
dp[i][j] + 1
} else {
std::cmp::max(dp[i+1][j], dp[i][j+1])
}
}
}
dp[n-1][n-1]
}
}