代码随想录算法训练营第四十六天|回文子串、最长回文子序列

回文子串 leetcode 647

解法一：动态规划

dp数组含义：bool类型dp[i][j]，[i,j]范围内是否为回文子串。

递推公式：当s[i]==s[j]时，有三种情况，第一种i=j此时肯定为回文子串，第二种j-i=1此时只有两个字符且相等也是回文子串，第三种情况j-i>1此时的dp[i][j]就和dp[i+1][j-1]有关了，如果dp[i+1][j-1]为true则i-j为回文子串。当s[i]!=s[j]那么i-j肯定不是回文子串此时dp[i][j]为false。

初始化：所有格子都初始化为false，则递推中就可以不讨论当s[i]!=s[j]的情况。

遍历顺序：根据递推公式得知，dp[i][j]和dp[i+1][j-1]有关，也就是当前格子是由其左下方格子推导而来，所以遍历顺序应该从下到上，从左到右。

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));int res=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){dp[i][j]=true;res++;}else if(dp[i+1][j-1]){dp[i][j]=true;res++;}}}}return res; }
};

解法二：双指针

思路：确定中心点向两边扩散判断是否为回文子串，中心点有两种情况，一种是以一个元素作为中心点，另一种是以两个元素作为中心点，分别对应回文子串大小为奇数和偶数时。

class Solution {
public: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;}int countSubstrings(string s) {int result=0;for(int i=0;i<s.size();i++){result+=extend(s,i,i,s.size());result+=extend(s,i,i+1,s.size());}return result;}
};

最长回文子序列 leetcode 516

解法一：动态规划

dp数组含义：[i,j]最长回文子序列长度为dp[i][j]。

递推公式：当s[i]==s[j]时，dp[i][j]=dp[i+1][j-1]+2。当s[i]!=s[j]时，有两种情况取i不取j或者取

j不取i然后取最大值，即dp[i][j]=max(dp[i][j-1],dp[i+1][j])。

初始化：最初始情况为i=j，所以将dp[i][j]=1(i==j)。

遍历顺序：从下到上，从左到右。

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][j-1],dp[i+1][j]);}}return dp[0][s.size()-1];}
};

因为i=j的情况已经初始化了，所以j从i+1开始遍历。

解法二：求s和反转s的最长公共子序列

dp数组含义：s以i为尾和t以j为尾的最长公共子序列长度为dp[i][j]。

class Solution {
public:int longestCommonSubsequence(const string& s,const string& t){vector<vector<int>> dp(s.size(),vector<int>(t.size(),0));for(int i=0;i<s.size();i++){if(s[i]==t[0]){for(int m=i;m<s.size();m++){dp[m][0]=1;}}}for(int j=0;j<t.size();j++){if(s[0]==t[j]){for(int n=j;n<t.size();n++){dp[0][n]=1;}}}for(int i=1;i<s.size();i++){for(int j=1;j<t.size();j++){if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}return dp[s.size()-1][t.size()-1];}int longestPalindromeSubseq(string s) {string t;for(int i=s.size()-1;i>=0;i--){t+=s[i];}return longestCommonSubsequence(s,t);}
};

dp数组含义：s以i-1为尾和t以j-1为尾的最长公共子序列长度为dp[i][j]。

class Solution {
public:int longestCommonSubsequence(const string& s, const string& t){vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}return dp[s.size()][t.size()];}int longestPalindromeSubseq(string s) {string t;for(int i=s.size()-1;i>=0;i--){t+=s[i];}return longestCommonSubsequence(s,t);}
};