算法训练营第60天|LeetCode 647.回文子串 516.最长回文子序列

LeetCode 647.回文子串

题目链接：

LeetCode 647.回文子串

代码：

class Solution {
public:int countSubstrings(string s) {int size = s.size();int result =0;vector<vector<int>>dp(size,vector<int>(size,false));for(int i = size-1;i>=0;i--){for(int j=i;j<size;j++){if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}}                }}return result;}
};

LeetCode 516.最长回文子序列

题目链接：

LeetCode 516.最长回文子序列

代码：

class Solution {
public:int longestPalindromeSubseq(string s) {int size = s.size();vector<vector<int>>dp(size,vector<int>(size,0));for(int i=0;i<size;i++) dp[i][i]=1;for(int i=size-1;i>=0;i--){for(int j=i+1;j<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][size-1];}
};