Longest Palindrome

发表于 | 分类于

Longest Palindrome

题目描述：

给定一个字符串，要求得到利用这个字符串的所有字符能够构成的最长的回文字符串的长度。

例子：

具体描述看LeetCode409

解题思路：

我们可以构建这个字符串的哈希表，然后根据每个字符数量的奇偶数来得到回文字符的长度。其中需要注意的地方是，如果有奇数个的字符的情况下，我们需要再回文字符的最终长度上加1.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int longestPalindrome(string s) {
        map<char, int> hash;
        int res = 0;
        int odd = 0;
        for (int i = 0; i < s.size(); i++){
            if (hash.find(s[i]) == hash.end()){
                hash.insert({s[i], 1});
            }else{
                hash[s[i]]++;
            }
        }//构建字符串的哈希表
        map<char, int>:: iterator it = hash.begin();
        while(it != hash.end()){
            if (it->second % 2 == 0){
                res += it->second;
                it++;
                //偶数的情况下直接将长度加到结果上
            }else{
                res += it->second - 1;
                odd++;
                it++;
                //奇数的情况下，加上减一后的偶数个，并将标志是否有奇数个字符的标志加1
            }
        }
        return (odd > 0) ? res + 1 : res;
        //最终长度加1
    }
};