题目描述
思路解析
一句话答案：LeetCode 2108 找出数组中的第一个回文字符串：从左往右遍历 words，每个词用首尾双指针向中间夹着判回文，先中的那个立即返回、一个都没有就返回空串，时间 O(L)、空间 O(1)。
words 里第一个回文串，返回的是哪个
给一个字符串数组 words，从前往后找，返回里面第一个正读反读都一样的词——也就是回文；一个回文都没有就返回空串 ""。题眼卡在「第一个」：哪怕后面有更长的回文，只要前面先冒出一个，答案就是前面那个，顺序动不得。
题面例子 words=["abc","car","ada","racecar","cool"] 返回 "ada"——racecar 也是回文，但 ada 排在它前面，先中先赢；words=["def","ghi"] 里两个都不是回文，返回空串 ""。
怎么判一个词是不是回文
回文就是正着读反着读一模一样，像 "ada"、"racecar"，也就是第一个和最后一个相同、第二个和倒数第二个相同，一路对到中间。直接的写法是把整串反过来跟原串比，相等就是回文，Python 一行 w==w[::-1] 就干这事；但反转要临时开一个等长副本，多花 O(k) 空间（k 是词长）。
首尾两根指针往中间夹，一对不等就出局
不反转也能判：摆两个下标，左指针 l 从第 0 位、右指针 r 从最后一位，每轮比 w[l] 和 w[r]。相等就 l 右挪、r 左挪，比下一对；只要有一对不等，这个词当场判死，不用再往里比。两指针在中间碰头（l 不再小于 r）都没撞上不等的，就是回文。
循环条件写 while l<r 就够：两指针相遇时中间那个字符是跟自己比、恒等，不必再看。这样只用两个下标、不开副本，空间 O(1)，奇数长度的词也照样能过。
为什么碰到第一个回文就得立刻返回
外层从左往右一个词一个词过，内层用上面的双指针判。判出是回文的那一刻必须马上 return、别再往后扫。题目要「第一个」，你要是扫完全程只留最后遇到的那个，返回的就可能是排在后面的回文，答案错位。反过来，前面的词都判了不是回文、外层才往右挪，所以第一个中的一定顺序最靠前。
题面那五个词，从头手算一遍
第一个词 "abc"：l=0 指 a、r=2 指 c，不等，出局。第二个 "car"：l=0 指 c、r=2 指 r，不等，出局。第三个 "ada"：l=0 指 a、r=2 指 a，相等，l 挪到 1、r 挪到 1，此时 l<r 不再成立、两指针相遇，没撞上任何不等的一对，判定是回文——它又是从左数第一个中的，立刻返回 "ada"，后面的 racecar、cool 根本不看。
再走 words=["def","ghi"]："def" 的 d 和 f 不等出局，"ghi" 的 g 和 i 不等出局，两个都判死，外层扫完没 return，返回空串 ""。
无解返回 null、条件写成 l≤r，都会埋雷
没有回文时题目要的是空串 "" 而非 null，返回 null 语义对不上、下游取值可能报错。内层条件写 l≤r 只是多比一次中心字符和自己（恒等、不出错），l<r 更干净。别以为回文非得偶数长度，"ada"、"level" 都是奇数长度的回文，双指针在中心处相遇自然通过。复杂度上最坏每个词从头比到尾、每个字符至多看一次，时间 O(L)（L 是总字符数）；双指针版只用两个下标，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套「一个词一个词过,每个词用首尾双指针向中间夹,先中的那个回文就是答案」,下面每一帧都在套它。
总览 · 四个词排成一排：这是数组 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题