leetcode409.Longest Palindrome

linkin 發(fā)布于2019-08-16 15:12 / 535人閱讀

摘要：題目要求輸入一個字符串，計(jì)算用這個字符串中的值構(gòu)成一個最長回?cái)?shù)的長度是多少。直觀來看，我們立刻就能想到統(tǒng)計(jì)字符串中每個字符出現(xiàn)的次數(shù)，如果該字符出現(xiàn)次數(shù)為偶數(shù)，則字符一定存在于回?cái)?shù)中。這個細(xì)節(jié)需要注意。

題目要求

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.

輸入一個字符串，計(jì)算用這個字符串中的值構(gòu)成一個最長回?cái)?shù)的長度是多少。

思路和代碼

這是一道easy難度的題目，但是一次性寫對也有挑戰(zhàn)。直觀來看，我們立刻就能想到統(tǒng)計(jì)字符串中每個字符出現(xiàn)的次數(shù)，如果該字符出現(xiàn)次數(shù)為偶數(shù)，則字符一定存在于回?cái)?shù)中。但是我們忽略了一點(diǎn)，即如果字符中存在一個額外的單個字符位于中間，該字符串也能構(gòu)成回?cái)?shù)，如aabaa。這個細(xì)節(jié)需要注意。
下面是O(N)時間的實(shí)現(xiàn)：

    public int longestPalindrome(String s) {
        int[] count = new int[52];
        int max = 0;
        for(char c : s.toCharArray()) {
            if(c>="a" && c<="z"){
                count[c-"a"]++;
                if(count[c-"a"] % 2 == 0) {
                    max +=2;
                }
            }
            
            if(c>="A" && c<="Z"){
                count[c-"A" + 26]++;
                if(count[c-"A"+26] % 2 == 0) {
                    max += 2;
                }
            }
        }
        
        if(max < s.length()) {
            max++;
        }
        return max;
    }