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

更新於 發佈於 閱讀時間約 4 分鐘
raw-image

這題的題目在這裡

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


測試範例:

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

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
題目敘述 Longest Palindromic Subsequence 給定一個字串s,請找出字串s的最長回文子序列的長度。 註: 子序列 不要求一定要連續。 測試範例 Input: s = "bbbab" Output: 4
Thumbnail
題目敘述 Longest Palindromic Subsequence 給定一個字串s,請找出字串s的最長回文子序列的長度。 註: 子序列 不要求一定要連續。 測試範例 Input: s = "bbbab" Output: 4
Thumbnail
題目敘述 Longest Palindromic Substring 給定一個輸入字串s,請找出最長的回文子字串。 答案可能不只一個,回傳任何一個合法的答案皆可。
Thumbnail
題目敘述 Longest Palindromic Substring 給定一個輸入字串s,請找出最長的回文子字串。 答案可能不只一個,回傳任何一個合法的答案皆可。
Thumbnail
給定一個字串s,以s擁有的字元製造迴文字串。要能製造出的迴文字串長度最長是多少,觀察迴文字串不外乎兩種模式對稱部分 + 核心字元 + 對稱部分,其中,核心字元在正中央出現一次,或者 對稱部分 + 對稱部分。使用演算法統計出現次數並推理出盡可能充分利用每個字元的迴文字串製造方法。
Thumbnail
給定一個字串s,以s擁有的字元製造迴文字串。要能製造出的迴文字串長度最長是多少,觀察迴文字串不外乎兩種模式對稱部分 + 核心字元 + 對稱部分,其中,核心字元在正中央出現一次,或者 對稱部分 + 對稱部分。使用演算法統計出現次數並推理出盡可能充分利用每個字元的迴文字串製造方法。
Thumbnail
題目敘述 輸入給定一個鏈結串列的head node。 要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉。 例如 5->2->13->3 5的右手邊有13,所以5刪除掉。 2的右手邊有13,所以2刪除掉。 13的右手邊沒有更大的節點,所以13留著。 3的右手邊沒有更大
Thumbnail
題目敘述 輸入給定一個鏈結串列的head node。 要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉。 例如 5->2->13->3 5的右手邊有13,所以5刪除掉。 2的右手邊有13,所以2刪除掉。 13的右手邊沒有更大的節點,所以13留著。 3的右手邊沒有更大
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定一個字串s,和指定長度k,問我們包含母音的子字串中,母音數量的最大值是多少? 題目的原文敘述 測試範例 Example 1: Input: s = "abciiidef", k = 3 Output: 3 Explanation: The substring "iii
Thumbnail
題目敘述 題目會給定一個字串s,和指定長度k,問我們包含母音的子字串中,母音數量的最大值是多少? 題目的原文敘述 測試範例 Example 1: Input: s = "abciiidef", k = 3 Output: 3 Explanation: The substring "iii
Thumbnail
題目敘述 題目會給定兩個輸入字串str1和str2,要求我們找出這兩個字串的最大共同子字串。 如果無解,則返回空字串""。 題目的原文敘述 測試範例 Example 1: Input: str1 = "ABCABC", str2 = "ABC" Output: "ABC" Exam
Thumbnail
題目敘述 題目會給定兩個輸入字串str1和str2,要求我們找出這兩個字串的最大共同子字串。 如果無解,則返回空字串""。 題目的原文敘述 測試範例 Example 1: Input: str1 = "ABCABC", str2 = "ABC" Output: "ABC" Exam
Thumbnail
這題也是滿經典的DP動態規劃教學案例和題目,就順便複習一下吧。 題目敘述 題目會給我們兩個字串text1, text2。 要求我們找出兩個字串的最長共同子序列,並且返回最長共同子序列的長度。 如果彼此沒有共同子序列,則返回0。 題目的原文敘述 測試範例 Example 1: In
Thumbnail
這題也是滿經典的DP動態規劃教學案例和題目,就順便複習一下吧。 題目敘述 題目會給我們兩個字串text1, text2。 要求我們找出兩個字串的最長共同子序列,並且返回最長共同子序列的長度。 如果彼此沒有共同子序列,則返回0。 題目的原文敘述 測試範例 Example 1: In
Thumbnail
題目 : 14. Longest Common Prefix
Thumbnail
題目 : 14. Longest Common Prefix
Thumbnail
題目會給定一個字串,問我們裡面最大的回文子字串內容為何? 本題目將用中心展開法來解題
Thumbnail
題目會給定一個字串,問我們裡面最大的回文子字串內容為何? 本題目將用中心展開法來解題
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News