Leetcode 516. Longest Palindromic Subsequence

tags: Leetcode(C++)

題目 : https://leetcode.com/problems/longest-palindromic-subsequence/ 。

想法 :

​​​​參考別人的想法才知道的，要把原本的字串先反轉過一次，再與原字串做LCS就知道最長廻文。

時間複雜度 : O(n^2)。

程式碼 :

class Solution {
public:
    int LCS(string in1, string in2){
        int l=in1.size(), dp[1010][1010]={0};
        
        for(int i=1 ; i<=l ; i++){
            for(int j=1 ; j<=l ; j++){
                if(in1[i-1] == in2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        return dp[l][l];
    }
    
    int longestPalindromeSubseq(string s) {
        string str=""+s;
        reverse(s.begin(), s.end());
        return LCS(s,str);
    }
};