經典字串題 最長回文子字串 Leetcode #5 Longest Palindromic Substring

這題的題目在這裡

題目會給定一個字串，問我們裡面最大的回文子字串內容為何?

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 <= 1000
• s consist 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