Problem can be convert to Longest Common Sequence if reverse s.C++ Solution


  • 0
    Y

    '''

    int longestPalindromeSubseq(string s) {
        string ss=s;
        reverse(s.begin(),s.end());//after reverse 
        int len=s.length();
        int dp[len+1][len+1];
        for(int i=0;i<=len;i++)
            dp[i][0]=dp[0][i]=0;
        
        for(int i=1;i<=len;i++){
            for(int j=1;j<=len;j++){
                if(s[i-1]==ss[j-1])
                    dp[i][j]=max(dp[i-1][j-1]+1,max(dp[i-1][j],dp[i][j-1]));
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[len][len];
    }
    

    '''


Log in to reply
 

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