學習目標：
用于記錄每日刷的題目為了明年的python組藍橋杯做準備，今天是打卡的第三天，沖！
原題：最長回文子串
題目描述：
給你一個字串
s，找到s中一個最長的回文子串，
示例一：
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案，
示例二：
輸入：s = "cbbd"
輸出："bb"
示例三：
輸入：s = "a"
輸出："a"
題解：
思路一(雙指標擴散法)：
1.首先我們知道一個回文子串肯定是中心對稱的，那么我們的思路就是選定一個字符為中心然后向這個字符的兩邊擴散，如果兩邊的字符相等，那么一定還是一個回文子串，直到出現兩邊的字符不相等，回傳此時的回文子串
2.以一個字符為中心擴散只能找到奇數長度的回文子串，所以我們還要去查找以偶數長度的子串，如果出現兩個相等的連續字符，我們以這兩個字符為中心向兩邊查找，直到兩邊的字符不相等回傳，
3.依此遍歷整個字串即可找到最大的子回文串，
代碼實作(Python) :
def longestPalindrome(s):
order =[0,0] #用于儲存最長回文子序列的下標
for i in range(len(s)-1):
l = i-1 ;r = i+1 ; index = [i,i] #查找奇數長度的回文串
while l >= 0 and r <= len(s)-1:
if s[l] == s[r]:
index[0],index[1] = l,r
else:
break
l -= 1
r += 1
if index[1] - index[0] > order[1] - order[0]: #重繪最大值
order[1],order[0] = index[1],index[0]
l = i; r = i+1 #查找偶數長度的回文串
if s[l] == s[r]:
index = [l,r]
while l >= 0 and r <= len(s)-1:
if s[l] == s[r]:
index[0],index[1] = l,r
else:
break
l -= 1
r += 1
if index[1] - index[0] > order[1] - order[0]: #重繪最大值
order[1],order[0] = index[1],index[0]
return s[order[0]:order[1]+1] #最后回傳最長的子回文串
C語言版:
#include <stdio.h>
#include <string.h>
int main()
{
int order1=0,order2=0,i,len,l,r,index1,index2;
char s[100];
gets(s); //獲取字串
len = strlen(s); //獲取字串長度
for(i=0;i<len-1;i++)
{
l=i-1;r=i+1;index1=i;index2=i; //查找奇數長度的最大子回文串
while(l>=0 && r<=len-1)
{
if(s[l]==s[r])
{
index1=l;index2=r;
}
else
{
break;
}
l -= 1;r += 1;
}
if((index2-index1)>(order2-order1)) //重繪最長子回文串的下標
{
order1 = index1;order2 = index2;
}
l=i;r=i+1;
if(s[l]==s[r])
{
l=l-1;r=r-1;index1=l;index2=r; //查找偶數長度的最大子回文串
while(l>=0 && r<=len-1)
{
if(s[l]==s[r])
{
index1=l;index2=r;
}
else
{
break;
}
l -= 1;r += 1;
}
if((index2-index1)>(order2-order1)) //重繪最長子回文串的下標
{
order1 = index1;order2 = index2;
}
}
}
for(i=order1;i<=order2;i++) //列印最長子回文串
{
printf("%c",s[i]);
}
printf("\n");
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/374776.html
標籤：python
上一篇：SpringBoot練手專案總結