题目描述
思路解析动画文字版
这个想法完全正确。我们可以换一种更动态的写法:边扫描边把字符凑成一对。
扫描结束后,length 是已经配成左右两边的长度;如果 odd 非空,就拿其中任意一个字符放中心,答案再加 1。
初始化:odd 为空,length=0:odd 里放暂时没有配对成功的字符。length 只统计已经能放到回文两边的成对字符。
读 'a':还没有配对,放进 odd:单独一个 a 暂时不能放到两边,只能先作为“可能的中心”候选留在 odd 里。
读 'b':也放进 odd:现在 odd={a,b},表示 a 和 b 都还没找到第二个相同字符。
读第一个 'c':放进 odd:第一个 c 也先放进 odd。
读第二个 'c':凑成一对,length += 2:高亮的两个 c 是刚凑成的一对,可以分别放在回文串左右两侧,所以 length 从 0 加到 2,c 从 odd 中移除。
第三个 'c':又变成未配对:字符出现次数的奇偶性在切换:第 3 个 c 让 c 再次变成未配对状态。
第四个 'c':再凑一对:高亮的两个 c 是第二对 c。四个 c 一共能贡献 4 个位置,全部放到回文串两边。
读第一个 'd':先放进 odd:第一个 d 还不能单独贡献两边的位置,先进入 odd 等待配对。
读第二个 'd':凑成第三对:高亮的两个 d 是第三对。它们贡献 2 个位置,现在已经配成的长度是 6,odd 里还剩 a 和 b。
odd 还非空:拿一个字符放中心:回文串最多只能有一个中心字符。odd 里虽然有 a 和 b 两个未配对字符,也只能任取一个放中心,最终答案是 7。
这一步只是帮你确认答案为什么是 7;真正代码仍然只维护 odd 和 length。
这题不需要真的拼出回文串。只要算出最多能放多少字符即可。
参考代码
class Solution: def longestPalindrome(self, s): odd = set() length = 0 for ch in s: if ch in odd: odd.remove(ch) length += 2 else: odd.add(ch) return length + (1 if odd else 0)复杂度
- 时间复杂度:O(n),每个字符扫描一次,集合操作平均 O(1)。
- 空间复杂度:O(1),英文字母大小写字符集有限,odd 大小有常数上界。
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
字母异位词分组
LeetCode 49 · 中等 · 沿着 哈希套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题