算法刷题记录 Day49

算法刷题记录 Day49

Date: 2024.04.17

lc 5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        // 1. dp. dp[i][j]表示s[i:j]是否是回文子串。
        // dp[i][j] = s[i] == s[j] && dp[i+1][j-1];
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        int max_len = 1;
        int startIdx = 0;
        //int endIdx = 0;
        // 初始化:所有长为1的串为true；
        for(int i=0; i<n; i++){
            dp[i][i] = true;
        }
        // 遍历顺序：自下而上，自左向右
        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){
                if(j == i+1 && s[i] == s[j]){
                    dp[i][j] = true;
                    if(2 > max_len){
                        max_len = max(max_len, 2);
                        startIdx = i;
                        //endIdx = j;
                    }                   
                }
                else if(s[i] == s[j] && dp[i+1][j-1]){
                    dp[i][j] = true;
                    if(j-i+1 > max_len){
                        max_len = max(max_len, j-i+1);
                        startIdx = i;
                        //endIdx = j;
                    }                 
                }
            }
        }
        return s.substr(startIdx, max_len);
    }
};

lc 647. 回文子串

class Solution {
public:
    int countSubstrings(string s) {
        // 我们判断回文子串的方式，是头==尾；
        // 因此，我们需要记录的状态是包含了子串的头和尾的；
        // dp[i][j]表示s[i, j]是否是回文子串;
        // dp[i][j] = dp[i+1][j-1] && s[i] == s[j];
        // 初始化所有i==j为true；
        int n = s.size();
        int count = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i=0; i<n; i++){
            dp[i][i] = true;
            count++;
        }
        
        // 由于状态由dp[i+1][j-1]推出，因此遍历时按自下而上，自左向右的顺序遍历;
        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){
                // 长为2，且两个字符相等;
                if(j == i+1 && s[i] == s[j]){
                    dp[i][j] = true;
                    count++;
                }
                else if(s[i] == s[j] && dp[i+1][j-1]){
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        return count;
    }
};

lc 516. 最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        // dp[i][j]表示s[i, j]中最长回文子序列长度.
        // dp[i][j] = max(dp[i][j], dp[i+k][j-k]+1) if s[i] == s[j] else 0;
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i=0; i<n; i++){
            dp[i][i] = 1;
        }

        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){
                if(s[i] == s[j] && j==i+1){
                    dp[i][j] = 2;
                }
                else if(s[i] == s[j]){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
                else{
                    dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};