这是悦乐书的第220次更新，第232篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第87题（顺位题号是409）。给定一个由小写或大写字母组成的字符串，找到可以用这些字母构建的最长的回文长度。这是区分大小写的，例如“Aa”在这里不被视为回文。例如：
输入：“abccccdd”
输出：7
说明：可以建造的最长的回文是“dccaccd”，其长度为7。
注意：假设给定字符串的长度不超过1,010。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
给定的字符范围是大小写字母，因此使用一个长度为256的整型数组，来存储字符串s中每个字符出现的次数。想要构成回文，字符串中的各个字符出现的次数分为两种情况：一是该字符出现偶数次，二是该字符出现奇数次。出现偶数次可以直接拿来使用，只要放在对称位置即可；出现奇数次时，如果是1次，那么该字符只能当做回文的中心且只能用一次，如果大于1次，则其偶数次部分可以直接使用，并且多余的1次可以当做回文的中心且只能使用一次。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public int longestPalindrome(String s) {
int[] arr = new int[256];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)]++;
}
int count = 0;
int single = 0;
for (int j=0; j<arr.length; j++) {
if (arr[j]%2 == 0) {
count += arr[j];
} else {
count += arr[j]-1;
single = 1;
}
}
return count+single;
}
03 第二种解法
此解法的思路和第一种解法一致，只是在计数判断那里有点区别。对数组中当前元素直接除以2得到商，再乘以2，得到当前字符可以使用的次数，但是同样需要判断奇数次元素，如果当前元素是奇数，并且count是偶数，即count之前没遇到奇数，那么count自加1，并且只会执行一次，因为回文字符串中心只能是一次。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public int longestPalindrome2(String s) {
int[] arr = new int[256];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)]++;
}
int count = 0;
for (int j=0; j<arr.length; j++) {
count += (arr[j]/2)*2;
if (arr[j]%2 == 1 && count%2 == 0) {
count++;
}
}
return count;
}
04 第三种解法
此解法思路和第二种解法一致，有区别的是判断出现奇数次字符并且count加1的逻辑从循环体中抽出来了，放在了最后。如果count和字符串s的长度做比较时，相等则说明s中的字符都是出现偶数次，不相等则说明s中有出现奇数次的字符，count就需要加1，且只能加1次。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public int longestPalindrome3(String s) {
int[] arr = new int[256];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)]++;
}
int count = 0;
for (int j=0; j<arr.length; j++) {
count += (arr[j]/2)*2;
}
return count == s.length() ? count : count+1;
}
05 第四种解法
使用HashSet，如果当前字符已经在set中存在，那么count加2，并且要移除当前字符；如果不存在，就add进set中。最后判断set是否为空，如果不为空，则说明有些字符出现了奇数次，就只能当做回文字符组中心来用，且只能用一次。
此解法的时间复杂度是O(n)，虽然使用了contains方法，但是HashSet内存储的数据不会达到O(n)规模，因此遍历判断是否包含当前字符需要的最多判断次数为52次，即O(52*n)，也即O(n)。
空间复杂度是O(1)，虽然使用了HashSet，但是字符的范围只是大小写字母，最大长度是52，可以看做是一个常量。
public int longestPalindrome4(String s) {
Set<Character> set = new HashSet<Character>();
int count = 0;
for (int i=0; i<s.length(); i++) {
if (set.contains(s.charAt(i))) {
count = count + 2;
set.remove(s.charAt(i));
} else {
set.add(s.charAt(i));
}
}
if (!set.isEmpty()) {
count = count + 1;
}
return count;
}
06 第五种解法
参照第四种解法的思路，我们同样可以使用数组来操作。数组的长度控制在58，因为a到z是从97到122，A到Z是从65到90，中间相隔58个数。将s变为字符数组，如果当前字符表示的十进制数，在数组中对应的元素为0就自加1，否则就自减1，然后count加2，最后再去判断数组中的元素有没有大于0的存在，如果存在即表示有字符出现了奇数次，然后count需要加1，且只用加一次。
public int longestPalindrome5(String s) {
int[] arr = new int[58];
int count = 0;
for (char ch : s.toCharArray()) {
if (arr[ch-'A'] == 0) {
arr[ch-'A']++;
} else {
arr[ch-'A']--;
count += 2;
}
}
for (int j=0; j<arr.length; j++) {
if (arr[j] > 0) {
count += 1;
break;
}
}
return count;
}
07 小结
算法专题目前已连续日更超过两个月，算法题文章87+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论