最长回文串-哈希表

已知一个只包括大小写字符的字符串，求用该字符串中的字符可以生 成的最长回文字符串长度。 例如 s = “abccccddaa”，可生成的最长回文字符串长度为9，如dccaaaccd、 adccbccda、 acdcacdca等，都是正确的。 LeetCode 409. Longest Palindrome

思考

例如在s = “abccccddaa”中，有3个a，1个b，4个c，2个d。 使用字符串s中的字符，任意组合，生成新的字符串，若生成的字符串为 回文字符串，需要除了中心字符，其余字符只要头部出现，尾部 就要对应出现。 例如: a...a、ccd...dcc、cc...d...cc

分析

例如，在s = “abccccddaa”中，有3个a，1个b，4个c，2个d。 1.在字符串中，字符数量为偶数的字符: 全部使用，头部放一个字符，尾部就对应放一个。 如，4个c和2个d可全部用上:...ccd...dcc...、...cdc...cdc...、...dcc...ccd...等。 2.在字符串中，字符数量为奇数的字符:丢掉一个字符，剩下的字符数为偶数个，按照字符数量为偶数的字符处理。 如，3个a中，有2个a可以用上:...a...a... 3.若有剩余的字符，如: 1个a、1个b 随便选择1个字符当作中心字符:...a...、...b...

算法设计

1.利用字符哈希方法，统计字符串中所有的字符数量; 2.设置最长回文串偶数字符长度为max_length = 0; 3.设置是否是否有中心点标记 flag = 0; 4.遍历每一个字符，字符数为count，若count为偶数，max_length += count;若count 为奇数，max_length += count – 1，flag = 1; 5.最终最长回文子串长度: max_length + flag。

class Solution{
public:
    int longestPalindrome(std::string s){
        int char_map[128]={0};字符哈希
        int max_length = 0;//回文串偶数部分最大长度
        int flag = 0;//是否有中心点
        for(int i = 0; i < s.length; i++){
            char_map[s[i]]++;
        }
        for(int i = 0; i < 128; i++){
            if(char_map[i] % 2 == 0){
                max_length += char_map[i];
            }
            else{
                max_length += char_map[i] - 1;
                flag = 1;
            } 
        }
        return max_length +flag;
    }
};

测试

int main(){
    std::string s= "abcdcccddaa";
    Solution solve;
    printf("%d\n",solve.longestPalindrome(s));
    return 0; 
}