Find First Palindromic String in the Array

Explore Solutions in Other Languages

Problem Description

Welcome to the world of palindromes, where words can be read the same way backward as forward! Imagine you’re at a party, and someone shouts, “Find the first palindromic string in this array!” You look around, and all you see are people trying to impress each other with their vocabulary. You think, “Why can’t they just say ‘racecar’ and call it a day?”

In this problem, you’re given an array of strings, and your mission—should you choose to accept it—is to find the first string that is a palindrome. If you can’t find one, just return an empty string. Easy peasy, right?

Code Solution


class Solution:
    def firstPalindrome(self, words: list[str]) -> str:
        def isPalindrome(s: str) -> bool:
            i = 0
            j = len(s) - 1
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True
        return next((word for word in words if isPalindrome(word)), '')

Approach

The approach here is as straightforward as a straight line—just like a palindrome! The code defines a helper function isPalindrome that checks if a given string reads the same backward. It uses two pointers, one starting from the beginning and the other from the end of the string, moving towards the center. If any characters don't match, it returns False. If all characters match, it returns True. The main function then iterates through the list of words and returns the first palindrome it finds, or an empty string if none exist.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity	O(1), as we are using a constant amount of space for the pointers and the return value.

Real-World Example

Imagine you're at a spelling bee, and the judge asks for a word that can be spelled the same way backward. You quickly think of "level" and "deified." But what if you had a list of words and needed to find the first one that fits the bill? That's exactly what this problem is about—finding that elusive palindromic word in a sea of ordinary words!