class Solution:
? ? def longestPalindrome(self, s):
? ? ? ? if (len(s) < 2):
? ? ? ? ? ? return s
? ? ? ? start = 0 ?#記錄最長回文子串開始的位置
? ? ? ? maxLen = 0 #記錄最長回文子串的長度
? ? ? ? for i in range(len(s) - 1):
? ? ? ? ? ? for j in range(i,len(s)):#j從i開始，不從i+1開始，s=‘ac'就能選第一個‘a'
? ? ? ? ? ? ? ? # 法一：截取所有子串，然后在逐個判斷是否是回文的
? ? ? ? ? ? ? ? # 法二（優化）：截取所有子串，如果截取的子串小于等于之前遍歷過的最大回文串，直接跳過。
? ? ? ? ? ? ? ? ? ? ? ? ? # 因為截取的子串即使是回文串也不可能是最大的，所以不需要判斷
? ? ? ? ? ? ? ? if (j - i < maxLen):
? ? ? ? ? ? ? ? ? ? continue
? ? ? ? ? ? ? ? if self.isPalindrome(s, i, j) and ?(maxLen < j - i + 1):
? ? ? ? ? ? ? ? # maxLen為最大長度時，后面maxLen<j-i+1 就為False,能保證截取最長回文字符串
? ? ? ? ? ? ? ? ? ? start = i
? ? ? ? ? ? ? ? ? ? maxLen = j - i + 1
? ? ? ? return s[start:start + maxLen]
?
? ? # 判斷是否是回文串
? ? def isPalindrome(self,s,start,end):
? ? ? ? while (start < end) :
? ? ? ? ? ? if s[start] != s[end]:
? ? ? ? ? ? ? ? ?return False
? ? ? ? ? ? start += 1
? ? ? ? ? ? end -= 1
? ? ? ? return True
?
s = ? "ac"
S = Solution()
result = S.longestPalindrome(s)
print(result)

class Solution:
? ? def longestPalindrome(self, s: str) -> str:
? ? ? ? # ?判斷空字符串的情況
? ? ? ? if (s == ""):
? ? ? ? ? ? return ""
? ? ? ? result = ""
? ? ? ? sSize = len(s)
? ? ? ? # 選擇一個中心點，向兩側擴展
? ? ? ? for i in range(sSize):
? ? ? ? ? ? # 奇數組情況
? ? ? ? ? ? tmpStr = self.expandHelper(s, i, i)
? ? ? ? ? ? # 偶數組情況
? ? ? ? ? ? tmpStr2 = self.expandHelper(s, i, i + 1)
? ? ? ? ? ? if len(tmpStr) > len(result):
? ? ? ? ? ? ? ? result = tmpStr
? ? ? ? ? ? if len(tmpStr2) > len(result):
? ? ? ? ? ? ? ? result = tmpStr2
? ? ? ? return result
?
? ? def expandHelper(self,s,left,right):
? ? ? ? sSize = len(s)
? ? ? ? while (left >= 0 and right < sSize and s[left] == s[right]):
? ? ? ? ? ? left -= 1
? ? ? ? ? ? right += 1
? ? ? ? # 小心s[left] != s[right]
? ? ? ? return s[(left + 1) : right]
?
?
s = "aaaabad"
S = Solution()
result = S.longestPalindrome(s)
print(result)

class Solution:
? ? def longestPalindrome(self, s):
? ? ? ? n = len(s)
? ? ? ? if n < 2:
? ? ? ? ? ? return s
?
? ? ? ? max_len = 1
? ? ? ? begin = 0
? ? ? ? # dp[i][j] 表示 s[i..j] 是否是回文串
? ? ? ? dp = [[False] * n for _ in range(n)]
? ? ? ? for i in range(n):
? ? ? ? ? ? dp[i][i] = True
?
? ? ? ? # 遞推開始
? ? ? ? # 先枚舉子串長度
? ? ? ? for L in range(2, n + 1):
? ? ? ? ? ? # 枚舉左邊界，左邊界的上限設置可以寬松一些
? ? ? ? ? ? for i in range(n):
? ? ? ? ? ? ? ? # 由 L 和 i 可以確定右邊界，即 j - i + 1 = L 得
? ? ? ? ? ? ? ? j = L + i - 1
? ? ? ? ? ? ? ? # 如果右邊界越界，就可以退出當前循環
? ? ? ? ? ? ? ? if j >= n:
? ? ? ? ? ? ? ? ? ? break
?
? ? ? ? ? ? ? ? if s[i] != s[j]:
? ? ? ? ? ? ? ? ? ? dp[i][j] = False
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? if j - i < 3:
? ? ? ? ? ? ? ? ? ? ? ? dp[i][j] = True
? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? dp[i][j] = dp[i + 1][j - 1]#只有dp[0][4]是True,dp[1][3]還是True……,這才是真正的回文串
? ? ? ? ? ? ? ? ? ? ? ? # dp[i][j] = True #假如s="abaa",s[0]=s[4], d[0][4]=True,就被認為是回文串，跳入下一個環節
?
? ? ? ? ? ? ? ? # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此時記錄回文長度和起始位置
? ? ? ? ? ? ? ? if dp[i][j] and j - i + 1 > max_len:
? ? ? ? ? ? ? ? ? ? max_len = j - i + 1
? ? ? ? ? ? ? ? ? ? begin = i
? ? ? ? return s[begin:begin + max_len]
?
?
s = "abaa"
S = Solution()
result = S.longestPalindrome(s)
print(result)

class Solution:
? ? def longestPalindrome(self, s: str) -> str:
? ? ? ? if not s :
? ? ? ? ? ? return ""
? ? ? ? res = ""
? ? ? ? n = len(s)
? ? ? ? dp = [[0] * n for _ in range(n)]
? ? ? ? max_len = float("-inf")
? ? ? ? for i in range(n):
? ? ? ? ? ? for j in range(i + 1):
? ? ? ? ? ? ? ? if s[i] == s[j] and (i - j < 2 or dp[j + 1][i - 1]):
? ? ? ? ? ? ? ? ? ? dp[j][i] = 1
? ? ? ? ? ? ? ? if dp[j][i] and ?max_len < i + 1 - j:
? ? ? ? ? ? ? ? ? ? res = s[j : i + 1]
? ? ? ? ? ? ? ? ? ? max_len = i + 1 - j
? ? ? ? return res

class Solution:
? ? def longestPalindrome(self, s: str) -> str:
? ? ? ? n = len(s)
? ? ? ? if n < 2:
? ? ? ? ? ? return s
? ? ? ?#中心擴展法，最直觀的方法
? ? ? ? def center_spread(L: int, R: int) -> str:
? ? ? ? ? ? while 0 <= L and R < n and s[L]==s[R]:
? ? ? ? ? ? ? ? L -= 1
? ? ? ? ? ? ? ? R += 1
? ? ? ? ? ? return s[L+1 : R]

? ? ? ? res = s[0]
? ? ? ? max_len = 1

? ? ? ? for i in range(n):
? ? ? ? ? ? odd_str = center_spread(i, i)
? ? ? ? ? ? even_str = center_spread(i, i+1)
? ? ? ? ? ??
? ? ? ? ? ? if len(odd_str) > len(even_str): ? ?#若長度為奇數的長
? ? ? ? ? ? ? ? if len(odd_str) > max_len:
? ? ? ? ? ? ? ? ? ? max_len = len(odd_str)
? ? ? ? ? ? ? ? ? ? res = odd_str
? ? ? ? ? ? else: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? #若長度為偶數的長
? ? ? ? ? ? ? ? if len(even_str) > max_len:
? ? ? ? ? ? ? ? ? ? max_len = len(even_str)
? ? ? ? ? ? ? ? ? ? res = even_str
? ? ? ??
? ? ? ? return res