Easy

题目描述

给定一个字符串数组 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] 只包含小写英文字母

提示：

  • 按顺序遍历元素。一旦当前元素是回文，就返回它。
  • 要检查一个元素是否为回文，你能反转字符串吗？

解题思路

解题思路

这道题要求找到数组中第一个回文字符串，思路比较直接：

  1. 遍历策略：按顺序遍历字符串数组，对每个字符串判断是否为回文

  2. 回文判断：有多种方法可以判断一个字符串是否为回文：

    • 方法一：使用双指针，从字符串两端向中间靠拢比较字符
    • 方法二：反转字符串，与原字符串比较是否相等
    • 方法三：使用递归判断

  3. 返回策略：一旦找到第一个回文字符串立即返回，如果遍历完所有字符串都没找到回文，则返回空字符串

推荐解法：使用双指针判断回文，这种方法时间复杂度最优，空间复杂度也最小。双指针方法通过设置左右两个指针，分别从字符串的开头和结尾开始，向中间移动并比较对应位置的字符。如果所有对应位置的字符都相等，则该字符串是回文。

这种方法的优势在于：

  • 不需要额外的空间来存储反转后的字符串
  • 一旦发现不匹配就可以提前退出
  • 代码简洁易懂

代码实现

class Solution {
public:
    string firstPalindrome(vector<string>& words) {
        for (const string& word : words) {
            if (isPalindrome(word)) {
                return word;
            }
        }
        return "";
    }
    
private:
    bool isPalindrome(const string& s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        def is_palindrome(s):
            left, right = 0, len(s) - 1
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        for word in words:
            if is_palindrome(word):
                return word
        return ""

public class Solution {
    public string FirstPalindrome(string[] words) {
        foreach (string word in words) {
            if (IsPalindrome(word)) {
                return word;
            }
        }
        return "";
    }
    
    private bool IsPalindrome(string s) {
        int left = 0, right = s.Length - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

var firstPalindrome = function(words) {
    const isPalindrome = (s) => {
        let left = 0, right = s.length - 1;
        while (left < right) {
            if (s[left] !== s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    };
    
    for (const word of words) {
        if (isPalindrome(word)) {
            return word;
        }
    }
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针解法
时间复杂度O(n × m)
空间复杂度O(1)

其中 n 是字符串数组的长度，m 是字符串的平均长度。在最坏情况下需要遍历所有字符串，并对每个字符串进行回文检查。

相关题目