25 - 回文串问题

1. 回文子串

法一：动态规划

递推公式
当s[i] != s[j]，那没啥好说的了，dp[i][j]一定是0。

当s[i]==s[j]，这就复杂一些了，有如下三种情况

• 下标i==j，同一个字符例如a，当然是回文子串
• 下标j - i==1，例如aa，也是回文子串
• 下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为1。

class Solution {
public:int countSubstrings(string s){int result = 0;vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])){dp[i][j] = 1;result++;}}}return result;}
};

时间复杂度O(n^2)，空间复杂度O(n^2)

法二：双指针法

首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。

在遍历中心点的时候，要注意中心点有两种情况：

• 一个元素可以作为中心点
• 两个元素也可以作为中心点。

那么有人同学问了，三个元素还可以做中心点呢。其实三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到。

class Solution {
public:int result = 0;int countSubstrings(string s) {for(int i = 0; i < s.size(); ++i){extend(s, i, i);extend(s, i, i + 1);}return result;}void extend(string s, int i, int j){while(i >= 0 && j < s.size() && s[i] == s[j]){result++;i--;j++;}}
};

时间复杂度O(n^2)，空间复杂度O(1)

2. 最长回文子串

其实和求回文子串思路一样可以采用两种方法，只不过加判断条件而已

方法一：动态规划法

class Solution {
public:string longestPalindrome(string s) {string result;if(s.size() < 1) return result;vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));int b = 0;int e = 0;for(int i = s.size() - 1; i >= 0; --i){for(int j = i; j < s.size(); ++j){if(s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])){dp[i][j] = 1;if(j - i > e - b){b = i;e = j;}}}}return s.substr(b, e - b + 1);}
};

方法二：双指针法

class Solution {
public:string longestPalindrome(string s) {int b = 0;int e = 0;for(int i = 0; i < s.size(); ++i){auto [left1, right1] = extend(s, i, i);auto [left2, right2] = extend(s, i, i + 1);if(right1 - left1 > e - b){b = left1;e = right1;}if(right2 - left2 > e - b){b = left2;e = right2;}}return s.substr(b, e - b + 1);}pair<int, int> extend(string s, int i, int j){while(i >= 0 && j < s.size() && s[i] == s[j]){i--;j++;}return {i + 1, j - 1};}
};

3. 最长回文子序列

确认递推公式

• s[i]==s[j]，那么dp[i][j] = dp[i + 1][j - 1] + 2;
• s[i]!=s[j]，那么说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。加入s[j]的回文子序列长度为dp[i + 1][j]，加入s[i]的回文子序列长度为dp[i][j - 1]。那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

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