> 文章列表 > leetcode:最长回文串(详解)

leetcode:最长回文串(详解)

leetcode:最长回文串(详解)

前言:内容包括:题目,代码实现,大致思路,代码解读

题目:

给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。

在构造过程中,请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:

输入:s = "a"
输出:1
示例 3:

输入:s = "aaaaaccc"
输出:7
 

提示:

1 <= s.length <= 2000
s 只由小写 和/或 大写英文字母组成

代码实现:
 

int longestPalindrome(char * s)
{int len = strlen(s);int arr[58] = { 0 };int i = 0;for (i = 0; i < len; i++){arr[s[i] - 'A']++;}int ret = 0;for (i = 0; i < 58; i++){ret += arr[i] - arr[i] % 2;}if (ret != len){ret += 1;}return ret;
}

大致思路:

回文串分两种:一种是全部由出现偶数次的字符构成 如abba

                         一种是由出现偶数次的字符+出现奇数次的字符构成 如 abcba

第二种回文串只允许有一个出现奇数次的字符

我们可以发现第一种回文串的长度是:所有出现偶数次的字符的个数之和

                      第二种回文串的长度是:所有出现偶数次的字符的个数之和+1

                       这个1就是唯一的一个被允许出现在回文串中的字符

1 统计s字符串中所有字符的个数

2 遍历存储所有字符个数的数组:

若是某个字符出现的次数是偶数次,则直接加上它的个数

若是出现的次数是奇数次,则加上它的个数-1

这样做的目标是使得这个出现奇数次的字符变成出现偶数次

3 比较ret和字符串s的长度len

   若是ret==len:表示该能构成的最长回文串全部都是由出现偶数次的字符构成的

   若是ret!=len:表示最长回文串是由出现偶数次的字符+出现奇数次的字符构成的

                             则最长回文串的长度是ret+1(ret中存储的是全部出现偶数次字符的个数之和)

代码解读:

 part 1 统计字符串s中所有字符的个数

    int arr[58] = { 0 };int i = 0;for (i = 0; i < len; i++){arr[s[i] - 'A']++;}

    开辟58个空间的原因是:

    字符串s中可以出现A~Z a~z

    要能存储以上字符的ASCII码值,按照最大空间来算,z的ASCII码值是122 

    z-'A' = 122-65 = 57       

part 2

	int ret = 0;for (i = 0; i < 58; i++){ret += arr[i] - arr[i] % 2;}if (ret != len){ret += 1;}return ret;

   ret:加上所有出现偶数次字符的个数

           若是某个字符出现了偶数次,直接加上它的个数

           若是某个字符出现了奇数次,需要加上它的个数-1,只加上它出现偶数次的部分