DEV Community

Miss Pooja Anilkumar Patel
Miss Pooja Anilkumar Patel

Posted on

516. Leetcode Solution in CPP

class Solution {
 public:
  int longestPalindromeSubseq(string s) {
    const int n = s.length();
    // dp[i][j] := LPS's length in s[i..j]
    dp.resize(n, vector<int>(n));
    return lps(s, 0, n - 1);
  }

 private:
  vector<vector<int>> dp;

  int lps(const string& s, int i, int j) {
    if (i > j)
      return 0;
    if (i == j)
      return 1;
    if (dp[i][j])
      return dp[i][j];

    if (s[i] == s[j])
      dp[i][j] = 2 + lps(s, i + 1, j - 1);
    else
      dp[i][j] = max(lps(s, i + 1, j), lps(s, i, j - 1));

    return dp[i][j];
  }
};

Enter fullscreen mode Exit fullscreen mode

leetcode

challenge

Here is the link for the problem:
https://leetcode.com/problems/longest-palindromic-subsequence/submissions/933388556/

Top comments (0)