2108-找出数组中的第一个回文字符串

给你一个字符串数组 words ，找出并返回数组中的 第一个回文字符串 。如果不存在满足要求的字符串，返回一个 空字符串 __""
。

回文字符串 的定义为：如果一个字符串正着读和反着读一样，那么该字符串就是一个 回文字符串 。

示例 1：

**输入：** words = ["abc","car","ada","racecar","cool"]
**输出：** "ada"
**解释：** 第一个回文字符串是 "ada" 。
注意，"racecar" 也是回文字符串，但它不是第一个。

示例 2：

**输入：** words = ["notapalindrome","racecar"]
**输出：** "racecar"
**解释：** 第一个也是唯一一个回文字符串是 "racecar" 。

示例 3：

**输入：** words = ["def","ghi"]
**输出：** ""
**解释：** 不存在回文字符串，所以返回一个空字符串。

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 仅由小写英文字母组成

方法一：逐个判断

思路与算法

为了寻找字符串数组 words 中第一个回文字符串，我们按顺序遍历数组，并依次判断每个字符串是否回文。如果当前字符串回文，则该字符串即为第一个回文字符串，我们返回该字符串作为答案；如果遍历完成仍未找到回文字符串，则返回空字符串作为答案。

一种判断字符串回文的方法是逐字符与反转后的对应字符比较是否相等。这里我们用函数 isPalindrome}(\textit{word}) 来判断字符串 word 是否为回文字符串。具体地，假设 word 的长度为 n，我们用 l, r 两个下标遍历反转前后的对应下标，其中 l 的初值为 0 代表字符串的起始字符，r 的初值为 n - 1 代表字符串的末尾字符。当 l < r 时，我们循环判断字符 word}[l] 与 word}[r] 是否相等：如果不相等，则说明 word 不为回文字符串，此时直接返回 false；如果相等，则我们将 l 加上 1 并将 r 减去 1 继续判断。如果循环结束时所有遍历的字符对均相等，此时无论 l = r 还是 l > r 都可以保证每个字符均与反转后对应位置的字符相等，因此 word 为回文字符串，此时应返回 true。

代码

[sol1-C++]

class Solution {
public:
    string firstPalindrome(vector<string>& words) {
        // 判断字符串是否回文
        auto isPalindrome = [](const string& word) -> bool {
            int n = word.size();
            int l = 0, r = n - 1;
            while (l < r) {
                if (word[l] != word[r]) {
                    return false;
                }
                ++l;
                --r;
            }
            return true;
        };
        
        // 顺序遍历字符串数组，如果遇到回文字符串则返回，未遇到则返回空字符串
        for (const string& word: words) {
            if (isPalindrome(word)) {
                return word;
            }
        }
        return "";
    }
};

[sol1-Python3]

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        # 判断字符串是否回文
        def isPalindrome(word: str) -> bool:
            n = len(word)
            l, r = 0, n - 1
            while l < r:
                if word[l] != word[r]:
                    return False
                l += 1
                r -= 1
            return True
        
        # 顺序遍历字符串数组，如果遇到回文字符串则返回，未遇到则返回空字符串
        for word in words:
            if isPalindrome(word):
                return word
        return ""

复杂度分析

• 时间复杂度：O(\sum_i n_i)，其中 n_i 为 words 数组中第 i 个字符串的长度。即为遍历寻找第一个回文字符串的时间复杂度。

• 空间复杂度：O(1)。