给定一堆长度为2的字符串,问最长可以构成多长的回文字符串
用python字典统计每一种长度2的字符串i出现的次数dict_word[i]
将长度为2的字符串分为两类:
第一类:ab型,即两个字母不同,那么需要找对应的ba字符串
ans = ans + 4 * min(dict_word[‘ab’], dict_word[‘ba’])
第一类:aa型,即两个字母不同,如果dict_word[‘aa’]出现奇数次,那么多出来的那一个只能放中间(如果有不止一个aa型字符串,且出现字数不止一次出现奇数,那正中间位置也只能放一个
ans = ans + 4 * (dict_word[i] // 2) + double_chr * 2 (double_chr记录是否出现过奇数次的aa型字符串)
1 #2131
2 #Runtime: 1376 ms
3 #Memory Usage: 37.8 MB
4
5 class Solution(object):
6 def longestPalindrome(self, words):
7 """
8 :type words: List[str]
9 :rtype: int
10 """
11 dict_word = {}
12 for i in words:
13 if i in dict_word:
14 dict_word[i] += 1
15 else:
16 dict_word[i] = 1
17 ans = 0
18 double_chr = 0
19 for i in dict_word:
20 j = i[::-1]
21 if i == j:
22 if dict_word[i] % 2:
23 double_chr = 1
24 ans += 4 * (dict_word[i] // 2)
25 else:
26 if j in dict_word:
27 ans += 4 * min(dict_word[i], dict_word[j])
28 dict_word[j] = 0
29 return ans + double_chr * 2