First Palindromic String in the Array
Problem
Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".
A string is a palindrome if it reads the same forwards and backwards. Check each word with two pointers that close in from both ends; return the first word that survives the check.
["abc", "car", "ada", "racecar", "cool"]"ada"def first_palindrome(words):
for w in words:
i, j = 0, len(w) - 1
while i < j and w[i] == w[j]:
i += 1
j -= 1
if i >= j:
return w
return ""function firstPalindrome(words) {
for (const w of words) {
let i = 0, j = w.length - 1;
while (i < j && w[i] === w[j]) { i++; j--; }
if (i >= j) return w;
}
return "";
}class Solution {
public String firstPalindrome(String[] words) {
for (String w : words) {
int i = 0, j = w.length() - 1;
while (i < j && w.charAt(i) == w.charAt(j)) { i++; j--; }
if (i >= j) return w;
}
return "";
}
}string firstPalindrome(vector<string>& words) {
for (string& w : words) {
int i = 0, j = (int)w.size() - 1;
while (i < j && w[i] == w[j]) { i++; j--; }
if (i >= j) return w;
}
return "";
}Explanation
We want the first palindrome, so the natural plan is to test the words in order and stop at the first one that passes. The interesting part is the palindrome test itself.
A word is a palindrome when its first and last characters match, and its second and second-to-last match, and so on toward the middle. Two pointers capture this perfectly: i starts at the front, j at the back, and they step inward together.
While i < j and the characters at those positions are equal, we keep closing in. The loop stops either because the pointers met or crossed (every pair matched) or because a pair differed. If i >= j when the loop ends, the word is a palindrome and we return it right away.
Because we return the instant a word passes, words after it are never examined — exactly the "first" semantics the problem asks for. If the loop over all words finishes with no palindrome found, we return the empty string.
Example: ["abc","car","ada","racecar","cool"]. "abc" fails at the first comparison (a vs c), "car" fails too (c vs r), then "ada" matches a/a and meets in the middle, so we return "ada".