leetcode409.Longest Palindrome

linkin 發布于2019-08-16 15:12 / 530人閱讀

摘要：題目要求輸入一個字符串，計算用這個字符串中的值構成一個最長回數的長度是多少。直觀來看，我們立刻就能想到統計字符串中每個字符出現的次數，如果該字符出現次數為偶數，則字符一定存在于回數中。這個細節需要注意。

題目要求

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.

輸入一個字符串，計算用這個字符串中的值構成一個最長回數的長度是多少。

思路和代碼

這是一道easy難度的題目，但是一次性寫對也有挑戰。直觀來看，我們立刻就能想到統計字符串中每個字符出現的次數，如果該字符出現次數為偶數，則字符一定存在于回數中。但是我們忽略了一點，即如果字符中存在一個額外的單個字符位于中間，該字符串也能構成回數，如aabaa。這個細節需要注意。
下面是O(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;
    }

GPU云服務器云服務器 palindrome Leetcod LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73342.html

LC 267 Palindrome Permutation II

摘要：判斷一個能否組成一個第一次出現增加一，第二次出現減少一。出現偶數次的最終對被抵消。出現基數詞的則會讓加一。類似于，奇數個的那個單獨考慮，必須放中間。得到各個字符一半數量的長度數字的終止條件，利用的對稱性輸出結果。 Given a string s, return all the palindromic permutations (without duplicates) of it. R...

lowett 2019-08-14 17:58 評論0 收藏0
[LeetCode/LintCode] Largest Palindrome Product

Problem Find the largest palindrome made from the product of two n-digit numbers. Since the result could be very large, you should return the largest palindrome mod 1337. Example Input: 2Output: 987Ex...

Barry_Ng 2019-08-15 18:16 評論0 收藏0
[Leetcode] Palindrome Permutation 回文變換

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結果中是否有回文。而中心對稱點如果是字符，該字符會是奇數次，如果在兩個字符之間，則所有字符都是出現偶數次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

svtter 2019-08-14 12:36 評論0 收藏0
[LeetCode/LintCode] Valid Palindrome

Valid Palindrome Problem Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Example A man, a plan, a canal: Panama is a palindrome. race a ca...

Ververica 2019-08-14 15:16 評論0 收藏0
[LeetCode] 9. Palindrome Number

Problem Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121Output: trueExample 2: Input: -121Output: falseExplana...

zhaochunqi 2019-08-16 13:43 評論0 收藏0