# Find First Palindromic String in the Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-first-palindromic-string-in-the-array)
Canonical: https://scaleengineer.com/dsa/problems/find-first-palindromic-string-in-the-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, String
---
## 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.

**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
## 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.
**Time:** 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:** 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:** 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.
### Explanation
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 `""`.

```java
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);
    }
}
```
### Algorithm
1. Iterate through each `word` in the `words` array.
2. For each `word`, call a helper function `isPalindrome(word)`.
3. 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.
4. If `isPalindrome(word)` returns `true`, return the current `word`.
5. If the loop completes without finding any palindromes, return an empty string `""`.

## Iterate and Check with Two Pointers
This is a more optimized approach. It also iterates through each string in the array, but the palindrome check is performed more efficiently using a two-pointer technique. This avoids creating a new string, thus saving space.
**Time:** O(N * K), where N is the number of strings and K is the maximum length of a string. We iterate through N words. For each word of length K, the two-pointer check takes O(K/2) which is O(K) time. · **Space:** O(1). The two-pointer check is done in-place and uses only a constant amount of extra space for the pointers, regardless of the input string's length.
**Pros:** Highly efficient in terms of space complexity (O(1)).; Generally faster in practice than the reversal method because it avoids object creation and can terminate early as soon as a mismatch is found.
**Cons:** The implementation is slightly more manual compared to using a built-in reverse function.
### Explanation
Similar to the first approach, we iterate through the `words` array. The key difference is in the `isPalindrome` helper function. This function uses two pointers, `left` starting at the beginning of the string (index 0) and `right` starting at the end (index `length - 1`). The pointers move towards each other. In each step, we compare the characters at the `left` and `right` pointers. If at any point the characters do not match, we know it's not a palindrome, and the function returns `false`. If the pointers cross or meet (`left >= right`) without finding any mismatches, it means the string is a palindrome, and the function returns `true`. The main function returns the first word for which `isPalindrome` returns `true`. If the loop finishes, it returns an empty string.

```java
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;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
1. Iterate through each `word` in the `words` array.
2. For each `word`, call a helper function `isPalindrome(word)`.
3. In `isPalindrome(word)`:
   a. Initialize two pointers: `left = 0` and `right = word.length() - 1`.
   b. Loop while `left < right`.
   c. Inside the loop, check if `word.charAt(left)` is not equal to `word.charAt(right)`. If they are different, return `false`.
   d. Increment `left` and decrement `right`.
   e. If the loop completes, it means all characters matched, so return `true`.
4. If `isPalindrome(word)` returns `true`, return the current `word`.
5. If the loop completes, return an empty string `""`.

# Solutions
### Java

```java
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 "";
  }
}

```

### CPP

```cpp
class Solution {
public:
  string firstPalindrome(vector<string> &words) {
    for (auto &w : words) {
      bool ok = true;
      for (int i = 0, j = w.size() - 1; i < j; ++i, --j) {
        if (w[i] != w[j]) {
          ok = false;
        }
      }
      if (ok) {
        return w;
      }
    }
    return "";
  }
};

```

### Python

```python
class Solution:
    def firstPalindrome(
        self, words: List[str]) -> str: return next((w for w in words if w == w[:: - 1]), "")

```