代码随想录算法训练营第47天
LeetCode 647. 回文子串
链接
class Solution {
public:int countSubstrings(string s) {int res = 0;for(int i = 0; i < s.size(); i++) {res += extend(s, i, i, s.size());res += extend(s, i, i + 1, s.size());}return res;}int extend(const string& s, int i, int j, int n) {int res = 0;while(i >= 0 && j < n && s[i] == s[j]) {i--; j++; res++;}return res;}
};class Solution {
public:int countSubstrings(string s) {int res = 0;vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));// dp[i][j]取决于dp[i + 1][j - 1]// j:从小到大，i:从大到小for(int i = s.size() - 1; i >= 0; i--) {for(int j = i; j <= s.size(); j++) {if(s[i] != s[j]) {continue;}if(j - i <= 1) {dp[i][j] = true;res++;} else if(dp[i + 1][j - 1]) {dp[i][j] = true;res++;}}}return res;}
};LeetCode 516. 最长回文子序列
链接
class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));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];}
};