找出数组中的第一个回文字符串 图解题解

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)。

Python

from __future__ import annotations
from 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 = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        return next((w for w in words if w == w[::-1]), "")

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    string firstPalindrome(vector<string>& words) {
        for (auto& w : words) {
            bool ok = true;
            for (int i = 0, j = w.size() - 1; i < j; ++i, --j) {
                if (w[i] != w[j]) {
                    ok = false;
                }
            }
            if (ok) {
                return w;
            }
        }
        return "";
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public String firstPalindrome(String[] words) {
        for (String w : words) {
            boolean ok = true;
            for (int i = 0, j = w.length() - 1; i < j && ok; ++i, --j) {
                if (w.charAt(i) != w.charAt(j)) {
                    ok = false;
                }
            }
            if (ok) {
                return w;
            }
        }
        return "";
    }
}