❓ 409. 最长回文串
难度:简单
给定一个包含大写字母和小写字母的字符串 s
,返回 通过这些字母构造成的 最长的回文串 。
在构造过程中,请注意 区分大小写 。比如 "Aa"
不能当做一个回文字符串。
示例 1:
输入:s = “abccccdd”
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:
输入:s = “a”
输出:1
示例 3:
输入:s = “aaaaaccc”
输出:7
提示:
- 1 <= s.length <= 2000
-
s
只由小写 和/或 大写英文字母组成
💡思路:
法一:定长数组
由于字符串s
只包含大写字母和小写字母,而大写字母A ~ Z
的对应十进制ASCII码为65 ~ 90
;小x写字母a ~ z
的对应十进制ASCII码为97 ~ 122
,所以可以使用长度为 123
的整型数组来统计每个字符出现的个数:
- 如果是偶数个字符,则一定可以构造成回文字符串;
- 如果是奇数个字符,则所有奇数个字符都需要减去
1
,最后加上一个1
。
法二:哈希表
可以使用哈希表,统计每个字符出现的次数:
- 如果是偶数个字符,则一定可以构造成回文字符串;
- 如果是奇数个字符,则所有奇数个字符都需要减去
1
,最后加上一个1
。
🍁代码:(Java、C++)
法一:定长数组
Java
class Solution {
public int longestPalindrome(String s) {
int[] cnts = new int[123];
for(char c : s.toCharArray()){
cnts[c]++;
}
int longest = 0;
int hasOdd = 0;
for(int cnt : cnts){
longest += cnt % 2 == 0 ? cnt : cnt - 1;
if(cnt % 2 != 0) hasOdd = 1;
}
return longest + hasOdd;
}
}
C++
class Solution {
public:
int longestPalindrome(string s) {
vector<int> cnts(123);
for(char c : s){
cnts[c]++;
}
int longest = 0;
int hasOdd = 0;
for(int cnt : cnts){
longest += cnt % 2 == 0 ? cnt : cnt - 1;
if(cnt % 2 != 0) hasOdd = 1;
}
return longest + hasOdd;
}
};
法二:哈希表
Java
class Solution {
public int longestPalindrome(String s) {
Map<Character, Integer> numOfChar = new HashMap<>();
for(char c : s.toCharArray()){
numOfChar.put(c, numOfChar.getOrDefault(c, 0) + 1);
}
int longest = 0;
int hasOdd = 0;
for(char c : numOfChar.keySet()){
longest += numOfChar.get(c) % 2 == 0 ? numOfChar.get(c) : numOfChar.get(c) - 1;
if(numOfChar.get(c) % 2 != 0) hasOdd = 1;
}
return longest + hasOdd;
}
}
C++
class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char, int> numOfChar;
for(char c : s){
numOfChar[c]++;
}
int longest = 0;
int hasOdd = 0;
for(auto num : numOfChar){
longest += num.second % 2 == 0 ? num.second : num.second - 1;
if(num.second % 2 != 0) hasOdd = 1;
}
return longest + hasOdd;
}
};
🚀 运行结果:
🕔 复杂度分析:
-
时间复杂度:
O
(
n
)
O(n)
O(n),其中
n
为字符串s
的长度。 -
空间复杂度:
O
(
S
)
O(S)
O(S),其中
S
为字符集大小。法一:我们使用了一个长度为123
的数组,存储每个字符出现的次数。法二:哈希映射(HashMap
)来存储每个字符出现的次数,最多只会存储52
个键值对。
题目来源:力扣。文章来源:https://www.toymoban.com/news/detail-429467.html
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-429467.html
注: 如有不足,欢迎指正!
到了这里,关于【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!