Leetcode Longest Palindromic Subsequence problem solution

YASH PAL,

In this Leetcode Longest Palindromic Subsequence problem solution 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.

Leetcode Longest Palindromic Subsequence problem solution

Problem solution in Python.

class Solution:
    def longestPalindromeSubseq(self, s):

        if not s:
            return 0
        res = [[0 for i in range(len(s))] for i in range(len(s))]
        return self.helper(s, 0, len(s) - 1, res)

    def helper(self, inp, s, e, res):
        if s == e:
            return 1
        if s > e:
            return 0
        if res[s][e]:
            return res[s][e]
        if inp[s] == inp[e]:
            res[s][e] = 2 + self.helper(inp, s + 1, e - 1, res)
        else:
            res[s][e] = max(self.helper(inp, s + 1, e, res),
                         self.helper(inp, s, e - 1, res))
        return res[s][e]

Problem solution in Java.

class Solution {
    public int longestPalindromeSubseq(String s) {
       
        int n = s.length();
        StringBuilder b = new StringBuilder();         
        b.append(s);         
        b.reverse();
        return solve(s, b.toString(), n, n);
    
    }
    
  int solve(String str1, String str2, int n, int m){
        
        int[][] dp = new int[n + 1][m + 1];
        //initialize
        for(int i = 0; i < n + 1; i++){
            for(int j = 0; j < m + 1; j++){
                if(i == 0 || j == 0) dp[i][j] = 0;
            }
        }
        //main code
        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < m + 1; j++){
                if(str1.charAt(i - 1) == str2.charAt(j - 1)){
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
}

Problem solution in C++.

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n+1,vector<int>(n+1,0));
        for(int i=1;i<dp.size();i++)
        {
            for(int j=1;j<dp.size();j++)
            {
                if(s[i-1] == s[n-j])
                {
                    dp[i][j] = 1 + dp[i-1][j-1];
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][n];
    }
};

coding problems