leetcode|409. 最长回文串


409. 最长回文串

  • 题号:力扣409
  • 知识点:贪心,哈希,字符串
  • 目标完成度:44/150
  • 总结
    题干:
    leetcode|409. 最长回文串
    文章图片
【leetcode|409. 最长回文串】思路:
  • 1.回文字符串的样式:BAB
  • 2.我的想法是,首先要构成回文字符串,除了中间的那个类的字母数量可以是奇数个,其他的都必须是偶数个。
  • 3.如果s中的某类字母的个数是偶数2n个,则这2n个在构造回文字符串时都可以用上。
  • 4.如果s中的某类字母的个数是奇数2n+1个,则除了回文字符串中间位置可以允许放奇数个字符,其他位置用上2n个。
  • 5.那么放在中间的字母是哪一类呢?根据贪心思想,放奇数次字母中出现次数最多的那类字母,可以使最终的回文字符串长度最长
  • 6.实现方法:先建立一个字典,根据value(出现次数)的值,提取处奇数次的字母odd,偶数次的字母直接加到ans
  • 7.对odd排个序,把最大的那个奇数直接加到ans上,其他的出现次数减一再加到ans上。减一目的是为了凑成偶数次,构造回文字符串的对称结构。
class Solution: def longestPalindrome(self, s: str) -> int: dic = collections.Counter(s) odd = [] ans = 0 for key, value in dic.items(): if value%2 == 1: odd.append([key, value]) else: ans += value odd.sort(key=lambda arr:arr[1]) odd = odd[::-1] for i in range(len(odd)): if i == len(odd): # odd[0][1] 是出现奇数次的字母中出现次数最多的那个字母的字数,这个放在中间位置 ans += odd[i][1] else: ans += (odd[i][1]-1) return ans

    推荐阅读