美文网首页LeetCode
最长回文串-哈希表

最长回文串-哈希表

作者: 徐凯_xp | 来源:发表于2018-05-09 16:40 被阅读0次

    已知一个只包括大小写字符的字符串,求用该字符串中的字符可以生 成的最长回文字符串长度。
    例如 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; 
    }
    

    相关文章

      网友评论

        本文标题:最长回文串-哈希表

        本文链接:https://www.haomeiwen.com/subject/mhqorftx.html