Find First Palindromic String in the Array

EASY

Description

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 palindromic if it reads the same forward and backward.

Example 1:

Input: words = ["abc","car","ada","racecar","cool"]
Output: "ada"
Explanation: The first string that is palindromic is "ada".
Note that "racecar" is also palindromic, but it is not the first.

Example 2:

Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "racecar".

Example 3:

Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists only of lowercase English letters.

Approaches

Checkout 2 different approaches to solve Find First Palindromic String in the Array. Click on different approaches to view the approach and algorithm in detail.

Iterate and Check with String Reversal

This approach iterates through each string in the input array. For each string, it checks if it's a palindrome by creating a reversed copy of the string and comparing it with the original. The first string that matches its reversed version is returned.

Algorithm

Iterate through each word in the words array.
For each word, call a helper function isPalindrome(word).
In isPalindrome(word): a. Create a new StringBuilder object from the word. b. Reverse the StringBuilder. c. Convert the reversed StringBuilder back to a String. d. Compare the original word with the reversed string. Return true if they are equal, false otherwise.
If isPalindrome(word) returns true, return the current word.
If the loop completes without finding any palindromes, return an empty string "".

The main idea is to traverse the words array from the beginning. For each word, we create a helper function, isPalindrome, to determine if it's a palindrome. Inside isPalindrome, we use a StringBuilder to create a reversed version of the input string. We then convert the StringBuilder back to a String and compare it with the original string using the .equals() method. If isPalindrome returns true, we have found our first palindromic string, and we can immediately return it. If the loop finishes without finding any palindromes, it means no such string exists in the array, so we return an empty string "".

class Solution {
    public String firstPalindrome(String[] words) {
        for (String word : words) {
            if (isPalindrome(word)) {
                return word;
            }
        }
        return "";
    }

    private boolean isPalindrome(String s) {
        String reversed_s = new StringBuilder(s).reverse().toString();
        return s.equals(reversed_s);
    }
}

Complexity Analysis

Time Complexity: O(N * K), where N is the number of strings in the `words` array and K is the maximum length of a string in the array. We iterate through N words, and for each word of length K, reversing and comparing takes O(K) time.Space Complexity: O(K), where K is the maximum length of a string. This is because we need to create a new string (or `StringBuilder`) of length K to store the reversed version of the string for comparison.

Pros and Cons

Pros:

Simple to understand and implement.
Leverages built-in language features for string manipulation, leading to concise code.

Cons:

Less efficient in terms of space, as it requires extra memory to store the reversed string.
Can be slightly slower in practice due to the overhead of creating new string objects.

Code Solutions

Checking out 3 solutions in different languages for Find First Palindromic String in the Array. Click on different languages to view the code.

class Solution {
public
  String firstPalindrome(String[] words) {
    for (var w : words) {
      boolean ok = true;
      for (int i = 0, j = w.length() - 1; i < j && ok; ++i, --j) {
        if (w.charAt(i) != w.charAt(j)) {
          ok = false;
        }
      }
      if (ok) {
        return w;
      }
    }
    return "";
  }
}

Video Solution

Watch the video walkthrough for Find First Palindromic String in the Array

Patterns:

Two Pointers

Data Structures:

ArrayString