[leetcode]: 409. Longest Palindrome

àì夳堔傛蜴生んèń 2022-06-16 14:40 120阅读 0赞

# 1.题目 #

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.

翻译：一个只包含大小写字母的字符串，求由这个字符串中的字符可以组成的最长回文串的长度。

# 2.分析 #

回文字符串，按对称来看，除了最中间的字符，其他字符均出现偶数次。  
所以，对字符串中出现的字符计数，出现大于一次的字符取偶数次，最后再加上1

# 3.代码 #

int longestPalindrome(string s) {
        int* hashTable = new int[100]();
        for (char c : s) {
            ++hashTable[c - 'A'];
        }
        int length = 0;
        for (int i = 0; i < 100; i++) {
            if (hashTable[i] > 0) {
       //只取偶数个字符
                if (hashTable[i] % 2 == 0)
                    length += hashTable[i];
                else
                    length += hashTable[i] - 1;
            }
        }
        if (length < s.size())//可以有一个奇数字符
            length += 1;
        return length;
    }

参考了一个很不错的Python解法

def longestPalindrome(self, s):
        #偶数的最后1bit是0
        odds=sum(v&1 for v in collections.Counter(s).values())
        return len(s)-odds+bool(odds)

这个位运算很巧妙

def longestPalindrome(self, s):
        #1取反的结果前面的bit全是1，最后1bit是0。所以v&~1的结果全是偶数。
        use = sum(v & ~1 for v in collections.Counter(s).values())
        return use + (use < len(s))