已知一个只包括大小写字符的字符串,求用该字符串中的字符可以生 成的最长回文字符串长度。
例如 s = “abccccddaa”,可生成的最长回文字符串长度为9,如dccaaaccd、 adccbccda、 acdcacdca等,都是正确的。
LeetCode 409. Longest Palindrome
思考
例如在s = “abccccddaa”中,有3个a,1个b,4个c,2个d。 使用字符串s中的字符,任意组合,生成新的字符串,若生成的字符串为 回文字符串,需要除了中心字符,其余字符只要头部出现,尾部 就要对应出现。
例如: a...a、ccd...dcc、cc...d...cc
分析
例如,在s = “abccccddaa”中,有3个a,1个b,4个c,2个d。
1.在字符串中,字符数量为偶数的字符: 全部使用,头部放一个字符,尾部就对应放一个。 如,4个c和2个d可全部用上:...ccd...dcc...、...cdc...cdc...、...dcc...ccd...等。
2.在字符串中,字符数量为奇数的字符:丢掉一个字符,剩下的字符数为偶数个,按照字符数量为偶数的字符处理。 如,3个a中,有2个a可以用上:...a...a...
3.若有剩余的字符,如: 1个a、1个b
随便选择1个字符当作中心字符:...a...、...b...
算法设计
1.利用字符哈希方法,统计字符串中所有的字符数量;
2.设置最长回文串偶数字符长度为max_length = 0;
3.设置是否是否有中心点标记 flag = 0;
4.遍历每一个字符,字符数为count,若count为偶数,max_length += count;若count 为奇数,max_length += count – 1,flag = 1;
5.最终最长回文子串长度: max_length + flag。
class Solution{
public:
int longestPalindrome(std::string s){
int char_map[128]={0};字符哈希
int max_length = 0;//回文串偶数部分最大长度
int flag = 0;//是否有中心点
for(int i = 0; i < s.length; i++){
char_map[s[i]]++;
}
for(int i = 0; i < 128; i++){
if(char_map[i] % 2 == 0){
max_length += char_map[i];
}
else{
max_length += char_map[i] - 1;
flag = 1;
}
}
return max_length +flag;
}
};
测试
int main(){
std::string s= "abcdcccddaa";
Solution solve;
printf("%d\n",solve.longestPalindrome(s));
return 0;
}
网友评论