导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二

LeetCode-409.Longest Palindrome

题目

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.

翻译

给出由大写字母或小写字母组成的字符串,找出可由这些字母组成的最长的回文字符串。
大小写敏感,例如”Aa”在这里不是回文的。
注意:假设给出字符串的长度不超过1010.
例如:
输入:”abccccdd”
输出:7
解释:可构造的最长回文字符串为”dccaccd”,长度为7。

方法一

利用int数组,记录每个字母出现次数
ASCII中,65到90为A-Z,97到122为a-z,中间有6个字符,所以可以设立一个长度为58的int数组;
回文字符串有两种情况:A.全都是成对字符,B.除成对字符外,有一个单独的字符,
对每个字母出现次数判断,当对2求余为0时,直接计入总和,当对2求余为1时,计入偶数部分,同时更新标识位,最后结果加1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public int longestPalindrome(String s) {
boolean isSingle = false;
int[] chars = new int[58];
int sumLen = 0;

for (char c : s.toCharArray()) chars[c - 'A']++;

for (int i : chars) {
if (i % 2 == 0) sumLen += i;
else {
isSingle = true;
sumLen += i - 1;
}
}

return isSingle ? sumLen + 1 : sumLen;
}
}

Runtime: 9 ms

方法二

设立Set,每个字母出现第一次加入,第二次则删除,总数加2。若最后Set不为空,总数加1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int longestPalindrome(String s) {
Set<Character> chars = new HashSet<Character>();
int sumLen = 0;

for (char c : s.toCharArray()) {
if (chars.contains(c)) {
sumLen += 2;
chars.remove(c);
} else chars.add(c);
}

return chars.isEmpty() ? sumLen : sumLen + 1;
}
}

Runtime: 19 ms

参考:
http://blog.csdn.net/u012985132/article/details/52738055