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

这道题到底在问什么

输入

words = ["abc","car","ada","racecar","cool"]

输出

"ada"（racecar 也是回文,但 ada 在前）

输入

words = ["def","ghi"]

输出

""（一个回文都没有）

先想最直接的笨办法

这是数组 words,一共四个字符串:cat、abca、noon、kayak。我们的活儿是从最左边开始,一个一个拿去判断是不是回文,谁先中,谁就是答案。先记住这个顺序,因为题目要的是第一个,顺序错不得。（动画第 4 步）

最优解：一步一步想明白

1. 3记牢这套「一个词一个词过,每个词用首尾双指针向中间夹,先中的那个回文就是答案」,下面每一帧都在套它。
2. 4这是数组 words,一共四个字符串:cat、abca、noon、kayak。我们的活儿是从最左边开始,一个一个拿去判断是不是回文,谁先中,谁就是答案。先记住这个顺序,因为题目要的是第一个,顺序错不得。
3. 5外层循环从最左边开始,第一个词是 "cat"。把它单独拎出来,用首尾双指针检查它是不是回文。接下来切到字符视角,看这个词的每个字母。
4. 6把 "cat" 的字母一个个铺开。左指针 l 站在最左的第 0 位,右指针 r 站在最右的第 2 位。回文的判法就是让这两根指针一对一对地比,同时往中间走。
5. 7先把两根指针指的字符读出来:左边 l 指着 "c",右边 r 指着 "t"。回文的判断就是逐对看这两个字符相不相等,下一帧就来比它们。
6. 8比 l 指的 c 和 r 指的 t,两个字母不一样,标红。回文只要有一对首尾对不上,整个串就出局了,不用再往里比,可以直接判它不是回文。
7. 9"cat" 判定不是回文,在词表里把它标灰淘汰。外层循环往右挪一格,拿下一个词继续同样的检查。到目前为止还没找到回文,不能停。
8. 10前面的词都淘汰了,外层往后挪一格,现在检查 "abca"。同样的办法,首尾双指针夹一遍。接下来切到字符视角,看这个词的每个字母。
9. 11把 "abca" 的字母一个个铺开。左指针 l 站在最左的第 0 位,右指针 r 站在最右的第 3 位。回文的判法就是让这两根指针一对一对地比,同时往中间走。
10. 12先把两根指针指的字符读出来:左边 l 指着 "a",右边 r 指着 "a"。回文的判断就是逐对看这两个字符相不相等,下一帧就来比它们。
11. 13比 l 指的 a 和 r 指的 a,两个字母一样,这一对配上了,标绿。回文要求每一对首尾都相等,目前为止没问题,继续往里夹。
12. 14这一对过关,左指针往右挪一格到第 1 位,右指针往左挪一格到第 2 位,接着比下一对。
13. 15比 l 指的 b 和 r 指的 c,两个字母不一样,标红。回文只要有一对首尾对不上,整个串就出局了,不用再往里比,可以直接判它不是回文。
14. 16"abca" 判定不是回文,在词表里把它标灰淘汰。外层循环往右挪一格,拿下一个词继续同样的检查。到目前为止还没找到回文,不能停。
15. 17前面的词都淘汰了,外层往后挪一格,现在检查 "noon"。同样的办法,首尾双指针夹一遍。接下来切到字符视角,看这个词的每个字母。
16. 18把 "noon" 的字母一个个铺开。左指针 l 站在最左的第 0 位,右指针 r 站在最右的第 3 位。回文的判法就是让这两根指针一对一对地比,同时往中间走。
17. 19先把两根指针指的字符读出来:左边 l 指着 "n",右边 r 指着 "n"。回文的判断就是逐对看这两个字符相不相等,下一帧就来比它们。
18. 20比 l 指的 n 和 r 指的 n,两个字母一样,这一对配上了,标绿。回文要求每一对首尾都相等,目前为止没问题,继续往里夹。
19. 21这一对过关,左指针往右挪一格到第 1 位,右指针往左挪一格到第 2 位,接着比下一对。
20. 22比 l 指的 o 和 r 指的 o,两个字母一样,这一对配上了,标绿。回文要求每一对首尾都相等,目前为止没问题,继续往里夹。
21. 23两根指针在中间碰头了,l 已经不小于 r,说明从外到内每一对都比过、而且都相等,再没有要比的了。
22. 24"noon" 的每一对首尾都相等,正着读反着读一模一样,它就是回文。它又是从左往右第一个中的,那答案就是它,程序在这里立刻返回 "noon",后面还没看的词全都不用管了。
23. 25回到词表,"noon" 标绿,它就是第一个回文。注意它右边的 "kayak" 其实也是回文,但因为我们在 "noon" 这里就返回了,"kayak" 根本没被检查过。这正是「第一个」的含义:先中先赢,后面不看。
24. 26回放整个过程:"cat" 首尾 c 和 t 不等淘汰,"abca" 比到第二对 b 和 c 不等淘汰,"noon" 两对全等,是第一个回文,直接返回。灰色的是淘汰的,绿色的是答案。判定始终只看两条:外层顺序从前往后,内层首尾双指针一对不等就出局。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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]), "")

#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 "";
    }
};

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 "";
    }
}

复杂度

面试官可能追问