1 647. 回文子串

647. 回文子串

【解法1】纯暴力解法，应该是O（n^3），居然AC了：

class Solution {
public:int countSubstrings(string s) {// 暴力int cnt = 0;cout << s.substr(1,1);for(int i = 0; i < s.size();i++){for(int j = i; j < s.size();j++){   string tmp = s.substr( i , (j-i+1));  // 为O（len）string reverse1 = tmp;reverse(tmp.begin(), tmp.end());  if(reverse1 == tmp)cnt++;}}return cnt;}
};

【解法2】动态规划。我按照经验的dp数组含义写，写不出，看了题解才懂。本题的dp数组和以往的不太一样，要回到回文串的本质，判断回文串的方法——当 [i,j] 确定是一个回文串时候，若i-1和j+1对应的字符一样，则可判断是一个回文串。

详见注释，AC代码：

class Solution {
public://int dp[1010]; // dp[i] 以i结尾的连续的字符串是回文子串的最大个数==>组合数目【错误】bool dp[1010][1010]; // dp[i][j]表示 s[i,j] 是一个回文串/*j >= iif(s[i] != s[j])dp[i][j] = 0;else{if(i == j) // 一个元素dp[i][j] = 1;else{if(j == i+1)dp[i][j] = 1;  //两个元素else  //至少3个元素{if(dp[i+1][j-1])dp[i][j] = 1;}}}初始化 dp[i][j] = 0;顺序：需要左下角是满的 i-- j++模拟——*/int countSubstrings(string s) {int ans = 0;for(int i = s.size()-1; i >= 0; i--){for(int j = i; j < s.size();j++){if(s[i] != s[j])dp[i][j] = 0;else{if(i == j) // 一个元素{dp[i][j] = 1;ans++;}else{if(j == i+1){dp[i][j] = 1;  //两个元素ans++;}else  //至少3个元素{if(dp[i+1][j-1]){dp[i][j] = 1;ans++;}}}}}}return ans;}
};

【解法3】双指针法。O(n^2)。

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

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

一个元素可以作为中心点，两个元素也可以作为中心点。那么有人同学问了，三个元素还可以做中心点呢。其实三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到。所以我们在计算的时候，要注意一个元素为中心点和两个元素为中心点的情况。

AC代码：

class Solution {
public:int count(string s,int l,int r){int ans = 0;while(l >= 0 && r < s.size() && s[l] == s[r]){l--;r++;ans++;}return ans;}int countSubstrings(string s) {int ans = 0;for(int i = 0; i < s.size();i++){// 以i为单点中心ans += count(s,i,i);// 以i为双点中心的左中心ans += count(s,i,i + 1);}return ans;}
};

5. 最长回文子串（类似的题）

用中心扩展双指针的做法：

class Solution {
public:int ans = 0;int max_l,max_r = 0;void count(string s,int l,int r){while(l >= 0 && r < s.size() && s[l] == s[r]){l--;r++;}l++;r--;if(r-l+1 > ans){max_l = l;max_r = r;ans = r-l+1 ;}}string longestPalindrome(string s) {for(int i = 0; i < s.size();i++){// 以i为单点中心count(s,i,i);// 以i为双点中心的左中心count(s,i,i + 1);}return s.substr(max_l,max_r - max_l + 1);}
};

2 516. 最长回文子序列

516. 最长回文子序列

我在学习完上一题的基础上，直接尝试推导这一题，因为我错误的dp数组含义：以i开头 j结尾的回文子序列的最大长度。结果状态转移方程弄的很复杂。还嵌套两个for循环。应该是能过很多测试点的，在第65个测试点 TLE 了。代码如下：

class Solution {
public:int dp[1010][1010]; // 以i开头 j结尾的回文子序列的最大长度/*if(s[i] != s[j])dp[i][j] = 0else{if(i == j)dp[i][j] = 1;   //一个元素else if(j == i+1)dp[i][j] = 2;   //两个元素else                             //至少三个元素 {int tmp = 0;for(int k1 = i+1; k1 <= j-1; k1++){for(int k2 = k1; k2<= j-1; k2++){tmp = max(tmp,dp[k1][k2]);}}if(tmp == 0)dp[i][j] = 0;else dp[i][j] = tmp+2;}}初始化：默认为0顺序：i--j++模拟：*/int longestPalindromeSubseq(string s) {int ans = 0;for(int i = s.size()-1; i >= 0; i--){for(int j = i; j < s.size();j++){if(s[i] != s[j])dp[i][j] = 0;else{if(i == j)dp[i][j] = 1;   //一个元素else if(j == i+1)dp[i][j] = 2;   //两个元素else                             //至少三个元素 {int tmp = 0;for(int k1 = i+1; k1 <= j-1; k1++)for(int k2 = k1; k2<= j-1; k2++)tmp = max(tmp,dp[k1][k2]);if(tmp == 0)dp[i][j] = 0;else dp[i][j] = tmp+2;}}ans = max(ans,dp[i][j]);}}return ans;}
};

学习完题解，要把dp数组的含义改成：以[i,j]中的回文子序列的最大长度。然后状态转移方程就比较好推导了。

AC代码：

class Solution {
public:int dp[1010][1010]; // 以[i,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]);去掉j元素   去掉i元素}初始化：默认为0,所以正对角线上全设置为1 ，便于状态转移的j循环从i+1开始顺序：i--j++模拟：*/int longestPalindromeSubseq(string s) {int ans = 1;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;elsedp[i][j] = max(dp[i+1][j],dp[i][j-1]);ans = max(ans,dp[i][j]);}}return ans;}
};