切換
舊版
前往
大廳
主題

LeetCode - 409. Longest Palindrome 解題心得

Not In My Back Yard | 2020-10-17 14:02:50 | 巴幣 0 | 人氣 168

題目連結:


題目意譯:
給定一字串 s ,其只由大小寫英文字母組成。回傳這些字母能組成的最長迴文之長度。

字母的大小寫差別視為相異。例如 "Aa" 在此並不算作一個迴文。

限制:
1 ≦ s.length ≦ 2000
s 只由小寫、大寫英文字母組成。



範例測資:
範例 1:
輸入: s = "abccccdd"
輸出: 7
解釋: 一個可以建構出的最長迴文為 "dccaccd",其長度為 7 。

範例 2:
輸入: s = "a"
輸出: 1

範例 3:
輸入: s = "bb"
輸出: 2


解題思維:
統計所有字母的出現次數,接著掃過這些出現次數。

對於每個字母的出現次數 T ,每兩個我們便可以將迴文加長,因此該字母會貢獻 T ÷ 2 取整 × 2 的長度(也就是找不超過 T 的最大偶數)。

接著因為迴文長度可以為奇數,其最中間的字母不需要與其他字元配對。因此,我們可以再掃過一次所有字母的出現次數去找有誰是出現奇數次的。如果有,則迴文長度又可以再 + 1(注意奇數長度迴文只會有一個中心,所以只能加一次)。

上面掃完之後,最後得出的迴文長度即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作