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

Examples

Example 1:

1
2
3
4

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:

1
2
3
4

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

Example 3:

1
2
3

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

Solution

Method 1 - Check for isPalindrome

To solve the problem of finding the first palindromic string in an array, we can follow these steps:

  1. Iterate through each string in the input array words.
  2. For each string, check if it reads the same forward and backward.
  3. Return the first string that satisfies the palindromic condition.
  4. If no such string is found, return an empty string "".

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

    private boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        for word in words:
            if self.is_palindrome(word):
                return word
        return ""
    
    def is_palindrome(self, s: str) -> bool:
        return s == s[::-1]

Complexity

  • ⏰ Time complexity: O(n * m), where n is the number of strings and m is the average length of the strings. This accounts for the iteration over each string and checking if it is a palindrome.
  • 🧺 Space complexity: O(1), since we are only using a constant amount of extra space for variables, excluding the space required for input storage.