2108. Find First Palindromic String in the Array

Problem Description

The problem asks us to find the first string in an array that is palindromic. A palindromic string is a string that reads the same forwards as it does backwards. For example, 'racecar' is a palindrome because reversing it gives the same word. We are given an array of strings and we need to check these strings one by one to see if any of them is a palindrome. The first palindromic string we come across should be returned. If we go through the whole array and find no palindromic strings, we return an empty string, represented by "".

Intuition

To solve this problem, the natural approach is to iterate over each string in the array and check whether it is a palindrome. If we find a palindrome, we return it immediately. To check if a string is a palindrome, we need to read it from the front and back and compare each character to see if they match. A convenient way to reverse a string in Python is to use the slicing syntax string[::-1], which creates a new string that is the reverse of the original.

Given that we want to find the first palindromic string, we can use Python's next function combined with a generator expression to efficiently look for it. The generator expression creates an iterator that will only process each string as needed, which is both memory efficient and potentially time-saving if the palindromic string is found early in the array. The next function then tries to get the first element from this generator, and if none is found, it returns a default value, which in this case is the empty string "". This succinctly solves the problem without needing extra loops or conditionals to handle the case where no palindromic string is found.

Learn more about Two Pointers patterns.

Solution Approach

The solution uses a generator expression that iterates over the list of words. This expression takes each word w in words and checks if it is a palindrome by comparing the word to its reverse, w[::-1]. This reversal is done using Python's slice notation, which, when provided with [::-1], starts from the end of the string and steps backwards, effectively reversing it.

Here's a step by step breakdown of the algorithm:

The generator expression (w for w in words if w == w[::-1]) creates an iterator. This iterator goes through each string w in the words array and yields it if and only if the string is the same as its reversed version. This leverages the fact that a palindrome is by definition a string that does not change when its characters are reversed.
Python’s next function is used to retrieve the next item from the iterator created by the generator expression. In this context, it serves to fetch the first palindrome it encounters while iterating over the generator.
The second argument to the next function is "", which is the default value to return in case the generator does not yield any items, i.e., if there are no palindromic strings in the array.

This solution is elegant and efficient:

It avoids the need for an explicit loop to iterate over the elements and check them one by one.
It uses lazy evaluation: the generator expression is only evaluated up to the point where the first palindrome is found, which can save time if a palindrome occurs early in the list.
There's no need for additional memory to store intermediate results, as the generator doesn't create a temporary list of palindromes, unlike, for example, a list comprehension would.

Overall, the use of next and a generator expression allows for an efficient and concise solution to the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach step by step. We have the following array of strings:

words = ["hello", "world", "racecar", "level", "sample"]

We are looking to find the first string that is palindromic.

The first string we check is "hello". We reverse it to see if it matches its original form: "olleh". Since "hello" is not equal to "olleh", we continue to the next word.
The next string is "world". Reversed, it is "dlrow", which again does not equal "world". So we move on.
We come to "racecar" and reverse it. The reversed version is "racecar" — it matches exactly! Since we found a palindrome, we don't need to check any further; we return "racecar".

To represent this process programmatically:

# use generator expression to iterate over each word and check if it is a palindrome
palindromic_string = next((w for w in words if w == w[::-1]), "")
print(palindromic_string)  # This will output "racecar"

The generator expression (w for w in words if w == w[::-1]) iterates through each word in the words array and yields the word if it is a palindrome. The next function is then used to get the first item from the iterator. If no palindromic string is found, it will return the default specified by the second argument, which is "".

In this example, the next function does not need to go through the entire list since it returns as soon as it finds the palindromic string "racecar". Thus, the generator stops iterating after the third element, demonstrating efficient use of resources. If racecar had not been a palindrome, the iteration would continue to "level", which is the next palindromic string, or until the list was exhausted.

Solution Implementation

1from typing import List  # Import List from the typing module for type hinting
2
3class Solution:
4    def firstPalindrome(self, words: List[str]) -> str:
5        """
6        Finds the first palindromic word from a list of words.
7
8        Args:
9        words (List[str]): A list of strings.
10
11        Returns:
12        str: The first palindromic word in the list of words, or an
13             empty string if there is no such word.
14        """
15        # Iterate through each word in the list
16        for word in words:
17            # Check if the current word is the same as its reversed copy
18            if word == word[::-1]:
19                return word  # Return the palindromic word
20
21        # Return an empty string if no palindromic word is found
22        return ""
23
24# Example usage:
25# sol = Solution()
26# print(sol.firstPalindrome(["abc", "car", "ada", "racecar", "cool"]))
27# This will print "ada" as it is the first palindrome in the list
28

1class Solution {
2    // This method finds the first palindromic string in an array.
3    public String firstPalindrome(String[] words) {
4        // Iterate over each word in the array.
5        for (String word : words) {
6            // Assume initially that each word could be a palindrome.
7            boolean isPalindrome = true;
8            // Use two pointers to compare characters from the front and the back.
9            for (int i = 0, j = word.length() - 1; i < j; ++i, --j) {
10                // If corresponding characters do not match, the word is not a palindrome.
11                if (word.charAt(i) != word.charAt(j)) {
12                    isPalindrome = false;
13                    // No need to check remaining characters if a mismatch is found.
14                    break;
15                }
16            }
17            // If the word is a palindrome, return it.
18            if (isPalindrome) {
19                return word;
20            }
21        }
22        // Return an empty string if no palindromic strings are found.
23        return "";
24    }
25}
26

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to find the first palindrome in a list of words.
7    string firstPalindrome(vector<string>& words) {
8        // Iterate over each word in the vector.
9        for (const auto& word : words) {
10            // Assume initially that the word is a palindrome.
11            bool isPalindrome = true;
12          
13            // Check each character from the start and the end of the word moving towards the center.
14            for (int start = 0, end = word.size() - 1; start < end; ++start, --end) {
15                // If the characters do not match, the word is not a palindrome.
16                if (word[start] != word[end]) {
17                    isPalindrome = false;
18                    break; // Exit the loop early as we already know it's not a palindrome.
19                }
20            }
21          
22            // If the word is a palindrome, return it.
23            if (isPalindrome) {
24                return word;
25            }
26        }
27      
28        // If no palindrome is found, return an empty string.
29        return "";
30    }
31};
32

1// This function searches for the first palindrome string within an array of words.
2// A palindrome is a word that reads the same backward as forward.
3// @param words - An array of strings to be checked.
4// @returns The first palindrome string if one exists, or an empty string if none is found.
5function firstPalindrome(words: string[]): string {
6    // Loop through each word in the array to check for palindromes.
7    for (const word of words) {
8        // Initialize pointers for the start and end of the word.
9        let startIndex = 0;
10        let endIndex = word.length - 1;
11
12        // Move the pointers towards the center of the word.
13        while (startIndex < endIndex) {
14            // Check if the characters at the start and end pointers do not match.
15            if (word[startIndex] !== word[endIndex]) {
16                // If they do not match, break from the loop; the word is not a palindrome.
17                break;
18            }
19            // Move the pointers closer to the center.
20            startIndex++;
21            endIndex--;
22        }
23
24        // If the pointers have met or crossed, the word is a palindrome.
25        if (startIndex >= endIndex) {
26            // Return the current palindrome word.
27            return word;
28        }
29    }
30  
31    // If no palindrome is found in the array, return an empty string.
32    return '';
33}
34

Time and Space Complexity

Time Complexity

The provided code checks each word in the list to see if it is a palindrome. The time it takes to check if a word is a palindrome depends on the length of the word, as it requires comparing characters from the beginning and the end towards the center.

To determine the time complexity, let n be the number of words in the list and k be the average length of these words.

Checking if a single word is a palindrome has a complexity of O(k) because we need to compare about half of the characters (in the worst case) to their counterparts on the other side of the word.

As we use a generator expression with the next function to find the first palindrome, the worst-case scenario happens when the palindrome is the last word in the list or there is no palindrome at all. Therefore, we might need to check every word. In this case, the time complexity would be O(n * k), as we perform an O(k) operation n times.

Space Complexity

The space complexity of the algorithm is O(1).

This is because it uses a constant amount of additional space regardless of the input size. The generator expression does not create an additional list in memory; it simply iterates over the existing list, and string slicing creates a new string, but since we are only interested in one word at a time, this does not accumulate with the number of words. Thus, the space used does not scale with the number of words n or their lengths k.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know