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

647. 回文子串

        

class Solution {
public:int countSubstrings(string s) {int sum=0;int n=s.size();vector<vector<int>> f(n+1,vector<int>(n+1,0));//表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串。初始值为0.for(int i = n-1;i>=0;i--){for(int j=i;j<n;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();vector<vector<int>> f(n,vector<int>(n,0)); //f[i][j]:从第i到j个字符回文串的最长长度for(int i=0;i<n;i++) f[i][i]=1;for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;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];}
};