Leetcode 2108: Find First Palindromic String in the Array

Input: You are given an array of strings, words, where each string consists of lowercase English letters.

Example: words = ["hello", "level", "world"]

Constraints:

• 1 <= words.length <= 100

• 1 <= words[i].length <= 100

• words[i] consists only of lowercase English letters

Output: Return the first palindromic word from the input array. If no such word exists, return an empty string.

Example: For words = ["hello", "level", "world"], the output should be "level".

Constraints:

Goal: The goal is to identify the first word in the array that is palindromic by checking if each word is equal to its reverse.

Steps:

• Iterate through each word in the array.

• For each word, check if it reads the same forward and backward.

• Return the first word that satisfies the condition. If no word satisfies the condition, return an empty string.

Goal: The constraints ensure that the solution must handle up to 100 words, each up to 100 characters long.

Steps:

• The length of the words array is at most 100.

• Each word's length is at most 100 characters.

Assumptions:

• All strings are lowercase English letters.

• The solution must identify palindromes efficiently.

• Input: Example 1: words = ["hello", "level", "world"]

• Explanation: The first palindromic word is "level", as it is the first word in the list that reads the same forward and backward.

• Input: Example 2: words = ["apple", "banana", "radar"]

• Explanation: The first palindromic word is "radar".

• Input: Example 3: words = ["dog", "cat"]

• Explanation: There are no palindromic words in the array, so the output is an empty string.

Approach: The problem requires iterating over the list of words and checking if each word is a palindrome. A palindrome is a word that reads the same backward as forward.

Observations:

• We can check if a word is a palindrome by comparing the word to its reverse.

• Since the constraints are small (up to 100 words, each with up to 100 characters), the solution can use a straightforward approach of checking each word.

• The solution is simple and works in O(n*m) time where n is the number of words and m is the average length of the words.

Steps:

• Loop through each word in the array.

• For each word, check if it is equal to its reverse.

• Return the first palindrome found. If no palindrome is found, return an empty string.

Empty Inputs:

• If the input array is empty, the function should return an empty string.

Large Inputs:

• If the input contains many long strings (up to the maximum constraints), the function should still operate efficiently.

Special Values:

• A single-character word is always a palindrome.

Constraints:

• The solution should handle up to 100 words, each with up to 100 characters.

string firstPalindrome(vector<string>& words) {
    for (auto &w : words)
        if (w == string(rbegin(w), rend(w)))
            return w;
    return "";
}

1 : Function Definition

string firstPalindrome(vector<string>& words) {

Define the function `firstPalindrome` that takes a vector of strings as an argument.

2 : Loop Start

    for (auto &w : words)

Start a loop to iterate through each word in the `words` vector.

3 : Condition Check

        if (w == string(rbegin(w), rend(w)))

Check if the current word `w` is equal to its reverse (using reverse iterators).

4 : Return Statement

            return w;

If a palindrome is found, return the current word `w`.

5 : Return Statement

    return "";

If no palindrome is found after checking all words, return an empty string.

Best Case: O(n)

Average Case: O(n*m)

Worst Case: O(n*m)

Description: The time complexity is O(n*m) where n is the number of words and m is the average length of the words.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) as the solution only requires a few additional variables to store intermediate results.

Leetcode 2108: Find First Palindromic String in the Array

Explore →