代码随想录算法训练营第五十七天| 647 回文子串 516 最长回文子序列

目录

647 回文子串

516 最长回文子序列

647 回文子串

在判断中dp[i][j]需要依赖dp[i + 1][j - 1]所以第一次循环应该从s.size() - 1到0。

因为j一定比i大，所以第二层循环应该从i到s.size()

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

时间复杂度O(n^2)

空间复杂度O(n^2)

516 最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));//dp[i][j]表示i到j之间最长回文子序列的个数
        for(int i = 0;i < s.size();i++)dp[i][i] = 1;
        for(int i = s.size() - 1;i >= 0;i--){
            for(int j = i + 1;j < s.size();j++){
                if(s[i] == s[j]){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = max(dp[i + 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.size() - 1];
    }
};

时间复杂度O(n^2)

空间复杂度O(n^2)