Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一堆长度为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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理