LeetCode 2108: Find First Palindromic String in the Array (Linear Scan + Two-Pointer Palindrome Check)
LeetCode 2108StringTwo PointersEasyToday we solve LeetCode 2108 - Find First Palindromic String in the Array.
Source: https://leetcode.com/problems/find-first-palindromic-string-in-the-array/
English
Problem Summary
Given an array of strings words, return the first string that is a palindrome. If none is palindromic, return an empty string.
Key Insight
The requirement is “first palindrome”, not “all palindromes”. So we should scan from left to right and stop at the first successful palindrome check.
Brute Force and Why It Is Already Good
A direct scan with a two-pointer palindrome test per word is already optimal for this problem style. Any approach that precomputes more structure gives no practical benefit here.
Optimal Algorithm (Step-by-Step)
1) Iterate each string w in words from index 0.
2) Use two pointers l=0, r=len(w)-1.
3) While l < r, compare w[l] and w[r].
4) If mismatch, this word is not palindrome; continue to next word.
5) If all pairs match, return this word immediately.
6) If loop finishes with no match, return "".
Complexity Analysis
Let total characters across all words be S.
Time: O(S) in worst case.
Space: O(1) extra space.
Common Pitfalls
- Forgetting to return immediately at the first palindrome.
- Using reversed-string allocation for every word (works but adds avoidable overhead).
- Mishandling empty string (it is a palindrome by definition).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String firstPalindrome(String[] words) {
for (String w : words) {
if (isPalindrome(w)) return w;
}
return "";
}
private boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l) != s.charAt(r)) return false;
l++;
r--;
}
return true;
}
}func firstPalindrome(words []string) string {
for _, w := range words {
if isPalindrome(w) {
return w
}
}
return ""
}
func isPalindrome(s string) bool {
l, r := 0, len(s)-1
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}class Solution {
public:
string firstPalindrome(vector<string>& words) {
for (const string& w : words) {
if (isPalindrome(w)) return w;
}
return "";
}
private:
bool isPalindrome(const string& s) {
int l = 0, r = (int)s.size() - 1;
while (l < r) {
if (s[l] != s[r]) return false;
++l;
--r;
}
return true;
}
};class Solution:
def firstPalindrome(self, words: List[str]) -> str:
for w in words:
if self.is_palindrome(w):
return w
return ""
def is_palindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return Truevar firstPalindrome = function(words) {
for (const w of words) {
if (isPalindrome(w)) return w;
}
return "";
};
function isPalindrome(s) {
let l = 0, r = s.length - 1;
while (l < r) {
if (s[l] !== s[r]) return false;
l++;
r--;
}
return true;
}中文
题目概述
给定字符串数组 words，返回其中第一个回文串；如果不存在回文串，返回空字符串。
核心思路
题目强调“第一个”，所以按原顺序线性扫描最自然。每个字符串用双指针从两端向中间检查，遇到首个回文就直接返回。
朴素方案为什么已经足够好
逐个单词检查回文就是最直接且高效的策略。做额外预处理通常不会降低总体复杂度，反而增加实现成本。
最优算法（步骤）
1）从左到右遍历数组中的每个字符串 w。
2）设置双指针 l=0、r=len(w)-1。
3）当 l < r 时比较两端字符。
4）若不相等，当前词不是回文，继续下一个词。
5）若全部匹配，立即返回该字符串。
6）遍历结束仍未命中，返回 ""。
复杂度分析
设所有字符串总长度为 S。
时间复杂度：O(S)；空间复杂度：O(1)（额外空间）。
常见陷阱
- 找到回文后没有立刻返回，导致结果不是“第一个”。
- 每个词都先生成反转字符串，额外开销较大。
- 忽略空串情况（空串本身是回文）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String firstPalindrome(String[] words) {
for (String w : words) {
if (isPalindrome(w)) return w;
}
return "";
}
private boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l) != s.charAt(r)) return false;
l++;
r--;
}
return true;
}
}func firstPalindrome(words []string) string {
for _, w := range words {
if isPalindrome(w) {
return w
}
}
return ""
}
func isPalindrome(s string) bool {
l, r := 0, len(s)-1
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}class Solution {
public:
string firstPalindrome(vector<string>& words) {
for (const string& w : words) {
if (isPalindrome(w)) return w;
}
return "";
}
private:
bool isPalindrome(const string& s) {
int l = 0, r = (int)s.size() - 1;
while (l < r) {
if (s[l] != s[r]) return false;
++l;
--r;
}
return true;
}
};class Solution:
def firstPalindrome(self, words: List[str]) -> str:
for w in words:
if self.is_palindrome(w):
return w
return ""
def is_palindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return Truevar firstPalindrome = function(words) {
for (const w of words) {
if (isPalindrome(w)) return w;
}
return "";
};
function isPalindrome(s) {
let l = 0, r = s.length - 1;
while (l < r) {
if (s[l] !== s[r]) return false;
l++;
r--;
}
return true;
}
Comments