题目描述
思路解析动画文字版
记牢这套「一个词一个词过,每个词用首尾双指针向中间夹,先中的那个回文就是答案」,下面每一帧都在套它。
总览 · 四个词排成一排：这是数组 words,一共四个字符串:cat、abca、noon、kayak。我们的活儿是从最左边开始,一个一个拿去判断是不是回文,谁先中,谁就是答案。先记住这个顺序,因为题目要的是第一个,顺序错不得。
外层遍历 · 检查第 0 个 "cat"：外层循环从最左边开始,第一个词是 "cat"。把它单独拎出来,用首尾双指针检查它是不是回文。接下来切到字符视角,看这个词的每个字母。
"cat" · 摆好首尾双指针：把 "cat" 的字母一个个铺开。左指针 l 站在最左的第 0 位,右指针 r 站在最右的第 2 位。回文的判法就是让这两根指针一对一对地比,同时往中间走。
"cat" · 先看两端指的字符：先把两根指针指的字符读出来:左边 l 指着 "c",右边 r 指着 "t"。回文的判断就是逐对看这两个字符相不相等,下一帧就来比它们。
"cat" · 比 c 和 t,不相等：比 l 指的 c 和 r 指的 t,两个字母不一样,标红。回文只要有一对首尾对不上,整个串就出局了,不用再往里比,可以直接判它不是回文。
淘汰 · "cat" 不是回文,看下一个："cat" 判定不是回文,在词表里把它标灰淘汰。外层循环往右挪一格,拿下一个词继续同样的检查。到目前为止还没找到回文,不能停。
外层遍历 · 检查第 1 个 "abca"：前面的词都淘汰了,外层往后挪一格,现在检查 "abca"。同样的办法,首尾双指针夹一遍。接下来切到字符视角,看这个词的每个字母。
"abca" · 摆好首尾双指针：把 "abca" 的字母一个个铺开。左指针 l 站在最左的第 0 位,右指针 r 站在最右的第 3 位。回文的判法就是让这两根指针一对一对地比,同时往中间走。
"abca" · 先看两端指的字符：先把两根指针指的字符读出来:左边 l 指着 "a",右边 r 指着 "a"。回文的判断就是逐对看这两个字符相不相等,下一帧就来比它们。
"abca" · 比 a 和 a,相等：比 l 指的 a 和 r 指的 a,两个字母一样,这一对配上了,标绿。回文要求每一对首尾都相等,目前为止没问题,继续往里夹。
"abca" · 双指针向中间收缩：这一对过关,左指针往右挪一格到第 1 位,右指针往左挪一格到第 2 位,接着比下一对。
"abca" · 比 b 和 c,不相等：比 l 指的 b 和 r 指的 c,两个字母不一样,标红。回文只要有一对首尾对不上,整个串就出局了,不用再往里比,可以直接判它不是回文。
淘汰 · "abca" 不是回文,看下一个："abca" 判定不是回文,在词表里把它标灰淘汰。外层循环往右挪一格,拿下一个词继续同样的检查。到目前为止还没找到回文,不能停。
外层遍历 · 检查第 2 个 "noon"：前面的词都淘汰了,外层往后挪一格,现在检查 "noon"。同样的办法,首尾双指针夹一遍。接下来切到字符视角,看这个词的每个字母。
"noon" · 摆好首尾双指针：把 "noon" 的字母一个个铺开。左指针 l 站在最左的第 0 位,右指针 r 站在最右的第 3 位。回文的判法就是让这两根指针一对一对地比,同时往中间走。
"noon" · 先看两端指的字符：先把两根指针指的字符读出来:左边 l 指着 "n",右边 r 指着 "n"。回文的判断就是逐对看这两个字符相不相等,下一帧就来比它们。
"noon" · 比 n 和 n,相等：比 l 指的 n 和 r 指的 n,两个字母一样,这一对配上了,标绿。回文要求每一对首尾都相等,目前为止没问题,继续往里夹。
"noon" · 双指针向中间收缩：这一对过关,左指针往右挪一格到第 1 位,右指针往左挪一格到第 2 位,接着比下一对。
"noon" · 比 o 和 o,相等：比 l 指的 o 和 r 指的 o,两个字母一样,这一对配上了,标绿。回文要求每一对首尾都相等,目前为止没问题,继续往里夹。
"noon" · 双指针向中间收缩：两根指针在中间碰头了,l 已经不小于 r,说明从外到内每一对都比过、而且都相等,再没有要比的了。
"noon" · 全部配对成功,是回文："noon" 的每一对首尾都相等,正着读反着读一模一样,它就是回文。它又是从左往右第一个中的,那答案就是它,程序在这里立刻返回 "noon",后面还没看的词全都不用管了。
命中 · "noon" 是第一个回文,返回：回到词表,"noon" 标绿,它就是第一个回文。注意它右边的 "kayak" 其实也是回文,但因为我们在 "noon" 这里就返回了,"kayak" 根本没被检查过。这正是「第一个」的含义:先中先赢,后面不看。
回放 · 答案就是 "noon"：回放整个过程:"cat" 首尾 c 和 t 不等淘汰,"abca" 比到第二对 b 和 c 不等淘汰,"noon" 两对全等,是第一个回文,直接返回。灰色的是淘汰的,绿色的是答案。判定始终只看两条:外层顺序从前往后,内层首尾双指针一对不等就出局。
边界想清:单个奇数回文照样返回、单字符必是回文取最前、全不是回文返回空串。
面试重点:C plus plus 与 Java 双指针、Python 整串反转;时间 O(L),双指针版空间 O(1)、Python 反转版临时 O(k);进阶可加过滤做忽略大小写的回文。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def firstPalindrome(self, words: List[str]) -> str: return next((w for w in words if w == w[::-1]), "")复杂度
- 时间：O(L)，L 是所有字符串的总长度。最坏情况每个词都要从头比到尾,每个字符至多被看一次,整体和总字符数成线性;命中越靠前实际越快
- 空间：O(1)，双指针只用两个下标,常数额外空间。要提醒的是 Python 那版用整串反转,会为当前词临时生成一个等长的反转副本,那一步是 O(k),k 为该词长度,不过是逐词临时占用,不累加
易错点
面试追问把动画讲成自己的话
追问三种语言的写法有什么区别?
追问这题的时间和空间复杂度是多少?
追问如果改成「忽略大小写和非字母字符」的回文判断,怎么处理?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最接近的三数之和
LeetCode 16 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题