[LeetCode]Longest Palindrome

题目描述:

LeetCode 409. Longest Palindrome

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.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

题目大意:

给定一个只包含小写或者大写字母的字符串,寻找用这些字母可以组成的最长回文串的长度。

大小写敏感,例如"Aa"在这里不认为是一个回文。

注意:

假设给定字符串的长度不超过1000。

解题思路:

统计每个字母的出现次数:

  若字母出现偶数次,则直接累加至最终结果

  若字母出现奇数次,则将其值-1之后累加至最终结果

若存在出现奇数次的字母,将最终结果+1

Python代码:

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans = odd = 0
        cnt = collections.Counter(s)
        for c in cnt:
            ans += cnt[c]
            if cnt[c] % 2 == 1:
                ans -= 1
                odd += 1
        return ans + (odd > 0)

 

本文链接:http://bookshadow.com/weblog/2016/10/02/leetcode-longest-palindrome/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码