代码随想录day57

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];}
};

647回文子串

两种做法 

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) { for (int j = i; j < s.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;}
};class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) { for (int j = i; j < s.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;}
};

5最长回文子串

class Solution {
public:string longestPalindrome(string s) {if(s.size()==1) return s;int maxlen=0;int index=0;for(int i=1;i<s.size();i++){for(int j=0;j<=1;j++){int slow=i-1;int fast=i+j;while(slow>=0&&fast<s.size()&&s[slow]==s[fast]){slow--;fast++;}if(maxlen<fast-slow-1){index=slow;maxlen=fast-slow-1;}}}return s.substr(index+1,maxlen);}
};