LeetCode – 最长回文串

• 2019 年 10 月 4 日
• 筆記

LeetCode第409题，难度简单。才发现两年前还用golang刷过几题，然而现在语法都忘完了。

原题地址：https://leetcode-cn.com/problems/longest-palindrome/

题目描述：

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:

假设字符串的长度不会超过 1010。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindrome

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

如果是要构造一个回文字符串，那么这个回文字符串中的字母肯定有两种情况：1. 所有字母的个数都是偶数；2. 大部分字母的个数都是偶数，只有一个字母的个数是奇数。

所以给定的字符串，我们先统计每个字符的个数，然后再判断偶数的个数（n & 1 = 1 则该数为奇数，否则为偶数）。最后，如果存在奇数，根据奇数的个数，由字符串长度减去奇数的个数再加1就是结果；如果没有奇数，直接返回。

中文官网题解：

https://leetcode-cn.com/problems/longest-palindrome/solution/

个人题解：

func longestPalindrome(s string) int {    var count ['z' - 'A' + 1]int    for _, c := range s {      count[c-'A']++    }    odd := 0    for c := 'A'; c <= 'z'; c++ {      odd += (count[c-'A'] & 1)    }    if odd> 0 {      return len(s) - odd + 1    } else {      return len(s) - odd    }  }

结果：

看上去这速度还不错。