[LeetCode] 409. Longest Palindrome 最长回文
2024-10-19 16:28:57
Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
This is case sensitive, for example "Aa"
is not considered a palindrome here.
Note:
Assume the length of given string will not exceed 1,010.
Example:
Input:
"abccccdd" Output:
7 Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.
给一个含有大写和小写字母的字符串, 找出能用这些字母组成的最长的回文。大小写敏感,字符长度不超过1010。
解法:由于字母可以随意组合,求出字符个数为偶数的字母,回文有两种形式,一种是左右完全对称,还有一种是以中间字符为中心,左右对称,统计出所有偶数个字符的出现总和,如果有奇数个字符的话,最后结果再加1。
Java:
public int longestPalindrome(String s) {
if(s==null || s.length()==0) return 0;
HashSet<Character> hs = new HashSet<Character>();
int count = 0;
for(int i=0; i<s.length(); i++){
if(hs.contains(s.charAt(i))){
hs.remove(s.charAt(i));
count++;
}else{
hs.add(s.charAt(i));
}
}
if(!hs.isEmpty()) return count*2+1;
return count*2;
}
Python:
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
ans = odd = 0
cnt = collections.Counter(s)
for c in cnt:
ans += cnt[c]
if cnt[c] % 2 == 1:
ans -= 1
odd += 1
return ans + (odd > 0)
Python:
class Solution(object):
def longestPalindrome(self, s):
map = {}
for i in s:
if i in map:
map[i] += 1
else:
map[i] = 1 odd, even = 0, 0
for key in map:
if map[key] % 2:
odd += 1
else:
even += 1 return even + 1 if odd else even
Python:
import collections class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
odds = 0
for k, v in collections.Counter(s).iteritems():
odds += v & 1
return len(s) - odds + int(odds > 0) def longestPalindrome2(self, s):
"""
:type s: str
:rtype: int
"""
odd = sum(map(lambda x: x & 1, collections.Counter(s).values()))
return len(s) - odd + int(odd > 0)
C++:
class Solution {
public:
int longestPalindrome(string s) {
int odds = 0;
for (auto c = 'A'; c <= 'z'; ++c) {
odds += count(s.cbegin(), s.cend(), c) & 1;
}
return s.length() - odds + (odds > 0);
}
};
类似题目:
[LeetCode] 5. Longest Palindromic Substring 最长回文子串
[LeetCode] 125. Valid Palindrome 有效回文
[LeetCode] 9. Palindrome Number 验证回文数字
[LeetCode] 516. Longest Palindromic Subsequence 最长回文子序列
All LeetCode Questions List 题目汇总
最新文章
- 再次思考 classpath 环境变量 等
- SMTP Error: Could not connect to SMTP host
- LINQ的基本认识
- PHP设计模式-策略模式 转
- linux下用Apache一个IP多个域名建虚拟主机
- nVivo highlight code中的文本
- TCP/IP 协议:IP 协议
- Oracle创建DBLink的方法
- 关于变量在for循环内外定义的思考
- BZOJ 1212: [HNOI2004]L语言( dp + trie )
- zoj 2067 White Rectangles
- valid palindrome(回文)
- java常用的框架介绍
- Python可变参数*和**
- 使用jsdelivr访问github资源
- Python学习第五堂课
- laravel get和all区别
- 列出下面几项的URL并解释每部分代表的含义
- Linux学习笔记13—Vi编辑器的学习
- ABP之事件总线(2)