题目
求最长回文子串
例子
moon: oo
abacdabba: abba
解题思路
思路1：
以每个字符为中心，分别从两边对称验证是否相等，注意分奇偶情况
时间复杂度：O(n*n)
代码1
class Solution {
public:string longestPalindrome(string s) {
if(s.size() < 2) return s;
int n = s.size(), maxLen = 0, start = 0;
for (int i = 0; i<n-1; ++i)
{//分奇偶searchPalindrom(s, i, i+1, start, maxLen);searchPalindrom(s,i,i,start, maxLen);
}
return s.substr(start, maxLen);}void searchPalindrom(string s, int left, int right, int& start, int& maxLen){while(left>=0 && right<s.size() && s[left] == s[right]){--left;++right;}if(maxLen < right-left-1){start =left +1;maxLen = right-left-1;}}
};
思路2：
方法1是利用了一个子函数处理了奇偶的不同情况，方法2直接在一个函数中解决：
- 在遍历到i时直接先判断一下相邻的是不是相等的，相等的就把它当偶数情况来处理，从两个数开始分别向两边比较；
- 另一个减少遍历的小技巧：在每次遍历之前都判断一下，剩下的字符串是否小于等于现在maxLen的一半，如果是的话，那最强也强不过现在的maxLen，所以就没有必要往下走了
代码2
class Solution {
public:string longestPalindrome(string s) {
//不使用子函数，直接在一个函数中处理奇偶的情况
if(s.size() <2) return s;
int n = s.size(), maxLen = 0, start = 0;
for(int i = 0; i<n; )//这边i要注意，不是直接++i，如果是偶数的话，下一个就往right后一个开始！
{if(n-i <=maxLen/2) break;//最理想情况全部符合回文也不会比现在得到的MaxLen大的，所以接下来的计算没必要int left = i, right = i;while(right <n -1 && s[right +1] == s[right]) ++right;//这一步就是在处理奇偶性，如果是偶数的回文串那么最中间的两个数是相等的，right和left是指在相邻的两个位置的，奇数情况的话两个数指在同一个位置上i = right+1;//为什么呢？因为left和right已经确定相等了，下一次遍历就从right+1开始while(right<n-1 && left >0 && s[right +1] == s[left -1]){++right; --left;}if(maxLen < right - left +1){maxLen = right-left+1;start = left;}
}
return s.substr(start, maxLen);}
};
思路3
用动态规划的思路，动态规划最重要的就是写出动态规划的公式：
- dp[i][j]表示字符串[i,j]，当i=j，即一个数√；当只有两个数，就判断s[i]和s[j]是否相等即可；当大于两个数时：s[i]==s[j]?? 且dp[i+1] [j-1]是否为回文
- 公式：
dp[i,j] = 1, i==j
s[j]==s[j] j=i+1
s[i]==s[j] &&dp[i+1][j-1] j>i+1
代码3
class Solution {
public:string longestPalindrome(string s) {
if(s.empty()) return "";
int n = s.size(), dp[n][n] = {0},left = 0, len = 1;//用动态规划解决(怎么着长度1是有的哇
for(int i = 0; i<n; ++i)//i是right，定right之后的left移动，看是否是回文串
{dp[i][i] = 1;for(int j = 0; j<i; ++j){dp[j][i] = (s[i]==s[j] && (i-j<2 || dp[j+1][i-1]));if(dp[j][i] && len< i-j+1){len = i-j+1;left = j;}}
}
return s.substr(left, len);}
};
思路4：参考网上的马拉车算法，将时间复杂度减小到线性
参考网址：马拉车算法的参考网址