Using Longest Common SubSequence C++ Code


  • 0
    class Solution {
    public:
        int longestPalindromeSubseq(string s) {
            
            // Just Reverse the String and Calculate Longest Common. Subsequence
            // between actual and reversed string.
            /*
            
            LCS(A,B)== 1+ LCS(A-1,B-1) if character are same
                        else 
                        max(LCS(A-1,B),LCS(A, B-1))
            
            
            */
            string s_rev=s;
            
            reverse(s_rev.begin(),s_rev.end());
            int n=s.size();
            
            int dp[n+1][n+1];
            for(int i=0;i<=n;i++)
            {
                dp[0][i]=0;
                dp[i][0]=0;
            }
            
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(s_rev[i-1]==s[j-1])
                    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];
            
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.