该题网址:https://leetcode.com/problems/longest-palindromic-substring/
这道题开始采用了最笨的方法,也是看到原题后的第一个思路,回文子串有两种
情况,一种是最中间为单个字符,另一种是中间有两个字符,所以我写了两
个循环,分别求出两种情况的最大回文子串的长度,然后比较那个大就返回
那个,所以最后的代码就跟屎一样长
class Solution {
public:
string longestPalindrome(string s) {
int l=s.length();
if(l==0) return s;
if(l==1) return s;
int tempsingle[l];//记录以该字符为中心最大回文子串的长度
int tempdouble[l]={0};//single和double分别表示中间为一或二的情况
int maxsingle=0,maxdouble=0;//最大长度
int indexsingle=0,indexdouble=0;//记录最大回文子串中间位置的字符的坐标
for(int i=1;i<l-1;i++)
{
tempsingle[i]=1;
int j=1;
while(s[i-j]==s[i+j])
{
tempsingle[i]+=2;
j++;
if(i-j<0&&i+j>=l)
{
break;
}
}
if(maxsingle<tempsingle[i])//更新最大子串信息
{
maxsingle=tempsingle[i];
indexsingle=i;
}
}
for(int i=0;i<l-1;i++)
{
int j=1;
while(s[i+1-j]==s[i+j])
{
tempdouble[i]+=2;
j++;
if(i-j<0&&i+j>=l)
{
break;
}
}
if(maxdouble<tempdouble[i])
{
maxdouble=tempdouble[i];
indexdouble=i;
}
}
string result;
if(maxsingle>maxdouble)//比较哪个的子串长
{
result=s.substr(indexsingle-maxsingle/2,maxsingle);
}
else
{
result=s.substr(indexdouble-maxdouble/2+1,maxdouble);
}
return result;
}
};
然后在网上找发现一个跟我的思想挺接近的一个实现算法,不过他的比较简练,下面是他实现的代码
回文的特点,就是中心对称。对于有N个字符的字符串S,只有2N-1个中心。为何是2N-1?因为两个字符之间的空档也可以是一个中心。例如”abba”的两个b中间就是一个中心。围绕一个中心检测回文需要O(N)时间,所以总的时间复杂度是O(N2)。
string expandAroundCenter(string s, int c1, int c2) {
int l = c1, r = c2;
int n = s.length();
while (l >= 0 && r <= n-1 && s[l] == s[r]) {
l--;
r++;
}
return s.substr(l+1, r-l-1);
}
string longestPalindromeSimple(string s) {
int n = s.length();
if (n == 0) return "";
string longest = s.substr(0, 1); // a single char itself is a palindrome
for (int i = 0; i < n-1; i++) {
string p1 = expandAroundCenter(s, i, i);
if (p1.length() > longest.length())
longest = p1;
string p2 = expandAroundCenter(s, i, i+1);
if (p2.length() > longest.length())
longest = p2;
}
return longest;
}