最长回文串
2020-03-19 本文已影响0人
环宇飞杨
题目
给定以个字符串,得出其重新排列后可组成最长的回文串长度。
回文串意思为, 不管从左到右读或从右到左读,均表现一致,比如单词level、noon,或中文的:上海自来水来自海上。
题目要求区分大小写:比如 Aba,不属于回文串。
示例
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
思路
- 如果某个字符x出现了偶数次,那么其出现的次数值一定是组成最终长度的一部分。
- 如果出现的是奇数次,那么x-1的值也是组成最终长度的一部分。
- 然后考虑特殊场景,当有字符出现奇数次时,其实是可以作为回文串的最中间部分存在的,但因为上一步中的x-1已经把这种场景全部减去掉了,所以需要找时机再加回来。
代码实现
- 遍历字符串,得出每个字符出现的次数。
- 新建变量res 存储回文串长度。
- 如果出现次数t为偶数 那么 res+=t;
- 如果出现次数为奇数 那么 res+=(t-1);
- 最终结果如果小于字符串长度,那么一定是因为有字母出现过奇数次被减掉了,需要再加回来。但是,不管出现过多少个奇数次,最终也只可有一个用来作为回文串中心,所以如果res<length时,res+=1 即可;
class Solution {
public int longestPalindrome(String s) {
int[] cnt = new int[58]; //A~Z,a~z 共58个字符,所以建立长度58的数组用于统计每个字符出现的次数。
for (char c : s.toCharArray()) {
cnt[c - 'A'] ++;
// 此处的c - 'A' 其实是用字符c和字符‘A’的ACK2码作差,得到的结果即为某个字符在cnt数组中的下标,比如字符c值为‘A’,那么下标为0,值为‘B’那么下标为1,值为‘a’下标为26,以此类推......是很巧妙也是被广泛运用的一种统计字符的方法;
}
int res = 0;
for (int t: cnt) {
// 字符出现的次数最多用偶数次。
if (t % 2 == 0){
res += t;
}else {
res += t -1;
}
}
if (res < s.length()){
res += 1;
}
return res;
}
}
复杂度
时间复杂度 O(2n)可以近似为O(n),空间复杂度中,因建立了个58长度的数组,多了空间占用,但因为并不会随着字符串长度的增加而增加,占用量为常数级别,所以依然算作O(1)。