該題網址:https://leetcode.com/problems/longest-palindromic-substring/
這道題開始采用了最笨的方法,也是看到原題後的第一個思路,回文子串有兩種
情況,一種是最中間為單個字元,另一種是中間有兩個字元,是以我寫了兩
個循環,分别求出兩種情況的最大回文子串的長度,然後比較那個大就傳回
那個,是以最後的代碼就跟屎一樣長
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIml2Zukncj9CX0xWdhZWZk9CX09Wbl9lcvRXakVGa49CXy9GdpRWZoh3LcRXZu5ibkN3Yuc2bsJmLjlGdhR3cvw1LcpDc0RHaiojIsJye.gif)
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;
}