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:
Time Complexity : O(n^2)
Space Complexity: O(n^2)
var longestPalindromeSubseq = function(s) {
const dp = [...Array(s.length)].map(() => Array(s.length).fill(0))
// Base case
for(let i = 0; i < s.length; i++) {
dp[i][i] = 1
}
for(let i = 1; i < s.length; i++) {
for(let j = 0; j < s.length; j++){
if(j+i < s.length){
// If the end letter and start letter are the same add 2 to the value in the bottom left diagonal. This value is a potential palindrome. If the letters are not equal set the current value to the previous highest palindrome subsequence
dp[j][j+i] = s[j] === s[j + i]
? dp[j+1][j+i-1] + 2
: Math.max(dp[j][j+i-1], dp[j+1][i+j])
}
}
}
return dp[0][s.length-1]
};
Top comments (1)
*JAVA | SIMPLE EXPLANATION | DETAILED CODE WITH COMMENTS
*
Simple Explanation of Bottom up DP Approach and Space Optimization. In PART 1, we had discussed Top Down DP approach.
youtube.com/watch?v=TqNrPslO8KE
SPACE OPTIMIZATION CODE