516. Longest Palindromic Subsequence

Problem

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.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
    var dp = Array(s.length).fill(0).map(() => Array(s.length));
    var helper = function(i, j) {
        if (j < i) return 0;
        if (dp[i][j] !== undefined) return dp[i][j];
        if (s[i] === s[j]) {
            dp[i][j] = (i === j ? 1 : 2) + helper(i + 1, j - 1);
        } else {
            dp[i][j] = Math.max(
                helper(i + 1, j),
                helper(i, j - 1),
                helper(i + 1, j - 1),
            );
        }
        return dp[i][j];
    };
    return helper(0, s.length - 1);
};

Explain:

nope.

Complexity:

• Time complexity : O(n * m).
• Space complexity : O(n * m).