Python编程题25--最长回文串的长度

题目

给定一个仅包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

注意：在构造过程中，字符串的字母可以按随意顺序组合成一个回文串，但需区分大小写，比如 "Aa" 不能当做一个回文字符串。

例如：

给定一个字符串："abccccdd"，返回结果：7

说明：上面字符构造的最长的回文串是"dccaccd"，其长度为 7

实现思路1

• 用 res 表示最长回文串的长度，用一个字典 tmp_dict 来统计字符串中每个字母出现的次数
• 遍历字典，如果字母出现的次数 i_count 为偶数，那么说明这些字母都可以用于构造回文串 res + i_count ；如果字母出现的次数 i_count 为奇数，那么最多只能把 i_count - 1 个用于构造回文串
• 最后判断 res 是否与原字符串 s 的长度一致，如果 res 等于 s 的长度，则说明所有字母统计次数均为偶数，直接返回 res 即可；如果 res 不等于 s 的长度，那么说明必然存在 i_count 为奇数，那么最后还可将 1 个奇数字符作为回文串的中位字符

代码实现

def longestPalindrome(s):
    res, tmp_dict = 0, {}
    for i in s:
        tmp_dict[i] = tmp_dict.get(i) + 1 if tmp_dict.get(i) else 1
    for i in tmp_dict:
        i_count = tmp_dict.get(i)
        res += i_count if i_count % 2 == 0 else i_count - 1
    return res if res == len(s) else res + 1

实现思路2

• 用集合 tmp_set 表示字符串中的不重复字母
• 遍历集合，利用Python的内置函数 count() 方法统计字母的出现个数，如果字母次数为偶数，则添加到列表 even_list ，如果字母次数为奇数，则只能向下取最大偶数个，并添加到列表 odd_list ；
• 最后，利用Python的内置函数 sum() 方法直接对 even_list 和 odd_list 求和，同时需判断 odd_list 是否为空，如果为空，那么直接返回求和结果即可；如果不为空，那么表示最后还可取一个字母作为回文串的中位字符

代码实现

def longestPalindrome(s):
    tmp_set = set(s)
    even_list = [s.count(i) for i in tmp_set if s.count(i) % 2 == 0]
    odd_list = [s.count(i) - 1 for i in tmp_set if s.count(i) % 2 != 0]
    if odd_list:
        return sum(even_list) + 1 + sum(odd_list)
    return sum(even_list) + sum(odd_list)

更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）