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 <= 1001 <= words[i].length <= 100words[i] consists only of lowercase English letters.This approach involves checking each string using a two-pointer technique. You set one pointer at the start and one at the end of the string and compare characters. If all characters match until the pointers cross, the string is a palindrome.
The function isPalindrome uses two pointers to check each character from both ends of a string. If they match all through, the string is a palindrome. The firstPalindrome function iterates through the list of words and returns the first palindromic string it finds.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1) because it uses constant space.
This method leverages string reversal to check if a word is a palindrome. You can reverse the string and compare it with the original; if they are the same, it's a palindrome.
The reverse function creates and returns a reversed version of the input string. In firstPalindrome, for each word in the array, it checks if the word equals its reversed counterpart, indicating it's a palindrome, and returns it.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), where n is the number of words and m is the length of words.
Space Complexity: O(m) due to the additional string for reversal.
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. |
| String Reversal Method | Time Complexity: O(n * m), where n is the number of words and m is the length of words. |
Find First Palindromic String in the Array - Leetcode 2108 - Python • NeetCodeIO • 11,030 views views
Watch 9 more video solutions →Practice Find First Palindromic String in the Array with our built-in code editor and test cases.
Practice on FleetCode