今日题目
思路
构成回文串一共有两种方式：
- 某个字符串在列表中存在其反转字符串
- 某个字符串本身就是回文串
其中，本身是回文串的字符串只能放在整个回文串的正中间。
解题方法
因此，我们可以用哈希表来解决这道题。 注意：先进行第一种情况的判断，再进行第二种情况的判断。 如果列表中存在某字符串的反转字符串，则将这两个字符串都加入结果中。
然后再判断该字符串本身是否为回文串。
复杂度
- 时间复杂度：
$O(N)$，N 为 words 的长度。
- 空间复杂度：
$O(N)$，N 为 words 的长度。
代码
class Solution:
def longestPalindrome(self, words: List[str]) -> int:
cnt = Counter(words)
ans = 0
sp = 0
for word, t in cnt.items():
# print(word, t)
if word[0] == word[1]:
ans += (t - t % 2)
sp |= (t % 2)
else:
ans += min(t, cnt[word[::-1]])
return (ans + sp) * 2
推广
更多题解请访问 我的博客