[leetcode-python]最长回文子串
题目：给你一个字符串 s，找到 s 中最长的回文子串
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
方案一：循环找
使用两个循环语句，第一个循环找回字文长度，第二个循环寻找回字文开头
class Solution:def longestPalindrome(self, s: str) -> str:def isPalindrome(st:str):#判断是否是回文字串num = round(len(st)/2)endS = -1for starS in range(num):if st[starS] != st[endS]:return FalseendS = endS -1return Trueif isPalindrome(s):return selif len(s) <= 1:return s[0]elif len(s) == 2:if isPalindrome(s):return selse :return s[0]else: lengthMax = 0 PalindromeLong = ''####最长的字符串for length in range(len(s)+1):####计算字符串长度for starS in range(0,len(s)-length):if isPalindrome(s[starS:starS + length + 1]):if length > lengthMax:lengthMax = lengthPalindromeLong = s[starS:starS + length + 1]if PalindromeLong == '':PalindromeLong = s[0]return PalindromeLong方案二：中心开花战略
顾名思义就是确定中心后，向两边搜索
class Solution:def longestPalindrome(self, s: str) -> str:def expand(s,left,right):###拓展两边，判断两边字符是否一致while left >= 0 and right < len(s) and s[left] == s[right]:left = left - 1right = right + 1###结束运行后，新的left 和right 已经不能满足条件了，所以left +1，right因为开闭口问题多取一位return left+1,rightPalindrome = ''lengthMAX = 0for minN in range(len(s)):##两种情况，单数和双数需要分开讨论##单数 需要中间一个开始数字双边leftN1,rightN1 = expand(s,minN,minN)##双数 需要中间两个开始数字双边leftN2,rightN2 = expand(s,minN,minN+1)if rightN1 - leftN1 > rightN2 - leftN2:xxx = s[leftN1 : rightN1]else :xxx = s[leftN2 : rightN2]if len(xxx) > lengthMAX:Palindrome = xxxlengthMAX = len(xxx)return Palindrome