代码随想录Day59 | 647. 回文子串 | 516. 最长回文子序列

647. 回文子串

        

class Solution {
public:
    int countSubstrings(string s) {
        int sum=0;
        int n=s.size();
        vectorint>> f(n+1,vector<int>(n+1,0));//表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串。初始值为0.
        for(int i = n-1;i>=0;i--){
            for(int j=i;j
/*如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的f[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。
所以一定要从下到上，从左到右遍历，这样保证f[i + 1][j - 1]都是经过计算的。*/
                if(s[i]==s[j]){  //如果判断的子串首尾字符相等
                    if(j-i<=1){  //子串长度为1或2，则一定是回文串
                        sum++;
                        f[i][j]=1;
                    }
                    else if(f[i+1][j-1]==1) //首部右移一个字符，尾部左移一个字符，仍是回文串，则就是回文串。
                    {
                        sum++;
                        f[i][j]=1;
                    }
                }
            }
        }
        return sum;
    }
};

516. 最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vectorint>> f(n,vector<int>(n,0)); //f[i][j]:从第i到j个字符回文串的最长长度
        for(int i=0;i1;
 
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j
                if(s[i]==s[j]){
                    f[i][j]=f[i+1][j-1]+2;
                }
                else{
                    f[i][j]=max(f[i+1][j],f[i][j-1]);
                }
            }
        }
        return f[0][n-1];
    }
};