題目:
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa" is not considered a palindrome here.
思路:
這一題如果只要回文長度的話,可以發現回文的組成仰賴於重複的字母,也就是說只要有一組重複的字母就可以構成回文裡面的2個數,比如說我們有 abbcdfghj ,那其中的 bb 就可以在裡面夠成 b_b,我們拆解這個題目就可以發現,我們只要統計每一個字母出現的次數,如果是偶數,比如說4次,那就代表這個字母可以構成4個回文中的字母,回文長度就 +4 ,如果是奇數,那也沒關係,那就代表偶數+1個,而這多出的一個就可以變成放在回文正中間的代表。
再近一步拆解,我們其實也不需要紀錄實際的偶數數量,我們只要紀錄無法成對的字母數量,然後再用原本的字串長度,剪掉這些(字母數量-1),-1是因為可以留一個在中央。
代碼:
def longestPalindrome(self, s):
odd = list()
for ch in s:
if ch not in odd:
odd.append(ch)
else:
#代表有一組重複了,所以這個字母需要重新計算
odd.remove(ch)
odd_num = len(odd)
if odd_num != 0:
return len(s) - odd_num + 1
else:
return len(s) - odd_num