leetcode409.Longest Palindrome

linkin 发布于2019-08-16 15:12 / 496人阅读

摘要：题目要求输入一个字符串，计算用这个字符串中的值构成一个最长回数的长度是多少。直观来看，我们立刻就能想到统计字符串中每个字符出现的次数，如果该字符出现次数为偶数，则字符一定存在于回数中。这个细节需要注意。

题目要求

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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