代码随想录训练营第46天|回文子序列

647. 回文子串

class Solution {
public:int count=0;void check(string& s, int left, int right){while(left>=0&&right<s.length()&&s[left]==s[right]){count++;left--;right++;}}int countSubstrings(string s) {for(int i=0; i<s.length(); i++){check(s,i,i);check(s,i,i+1);}return count;}
};

贪心解法，由中心向两边扩散，直至不相等，得到最大回文串。

遍历所有可能的中心，累计扩散过程所有的子串。

516. 最长回文子序列

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {text1.insert(text1.begin(),' ');text2.insert(text2.begin(),' ');int n1=text1.length(), n2=text2.length(), max_len=0;vector<vector<int>> dp(n1,vector<int>(n2,0));for(int i=1; i<n1; i++){for(int j=1; j<n2; j++){if(text1[i]==text2[j])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);max_len=max(max_len,dp[i][j]);}}return max_len;}int longestPalindromeSubseq(string s) {string r(s.rbegin(), s.rend());return longestCommonSubsequence(s,r);}
};

利用最长子序列解决回文子序列问题。