這題的題目在這裡
題目會給定一個字串，問我們裡面最大的回文子字串內容為何?
測試範例:
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
約束條件:
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
演算法:
逐一從左到右，掃描每個字元。
以每個字元當作中心，向兩側擴展，擴展的同時，檢查是否滿足回文字串的特性，頭尾相等。
每一輪擴展完，更新並且記錄，最長的回文子字串。
程式碼:
class Solution:
def longestPalindrome(self, s):
# get the longest palindrome, from left to right inclusively
# index grows from center to outer
def central_expansion_from(self, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left, right = left-1, right+1
return s[left+1:right]
longest_palindrome = ""
#scan each possible i as center index
for i in range(len(s)):
# Odd length, central expansion pattern: "s" -> "asa"
odd_len_palindrome = central_expansion_from(s, i, i)
if len(odd_len_palindrome) > len(longest_palindrome):
longest_palindrome = odd_len_palindrome
# Even length, central expansion pattern: "s" -> "assa"
even_len_palindrome = central_expansion_from(s, i, i+1)
if len(even_len_palindrome) > len(longest_palindrome):
longest_palindrome = even_len_palindrome
return longest_palindrome
要注意的部分就是，下標的部分要處理好，最後在central_expansion_from
function裡面，合法的回文子字串是s[left+1:right]
時間複雜度: O( n² )
外層for loop 掃描花費O(n), 內層回文字串比較while loop再花費O( n )
空間複雜度: O( n )
紀錄回文子字串，最長可能長度為O( n )
Reference:
[1] Python O(n²) by center expansion [w/ Comment] — Longest Palindromic Substring — LeetCode
