题目:最长回文串
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
复制代码
示例:
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
复制代码
思考:
这题先用一个Map记录每个字符出现的次数。
接着遍历Map,次数为偶数的可以接加入结果,次数为奇数的将次数减1后加入结果。
用一个布尔值记录一下是否有奇数次数的元素。
遍历Map结束后,如果有奇数次数元素,可以将一个奇数次数数字放在字符串中间,回文串长度加1。
复制代码
实现:
class Solution {
public int longestPalindrome(String s) {
int result = 0;
boolean isHas = false;
char[] strArray = s.toCharArray();
Map<Character, Integer> time = new HashMap();
for (int count = 0; count < strArray.length; count++) {
if (time.get(strArray[count]) == null) {
time.put(strArray[count], 1);
} else {
time.put(strArray[count], time.get(strArray[count]) + 1);
}
}
Set<Character> set = time.keySet();
for (Character character : set) {
int times = time.get(character);
if (times % 2 == 0) {
result += (times);
} else if (times % 2 == 1) {
isHas = true;
result += ((times - 1));
}
}
if (isHas) {
result += 1;
}
return result;
}
}复制代码