2108. Find First Palindromic String in the Array
Problem Description
The problem asks us to find the first string in an array that is palindromic. A palindromic string is a string that reads the same forwards as it does backwards. For example, 'racecar' is a palindrome because reversing it gives the same word. We are given an array of strings and we need to check these strings one by one to see if any of them is a palindrome. The first palindromic string we come across should be returned. If we go through the whole array and find no palindromic strings, we return an empty string, represented by "".
Intuition
To solve this problem, the natural approach is to iterate over each string in the array and check whether it is a palindrome. If we find a palindrome, we return it immediately. To check if a string is a palindrome, we need to read it from the front and back and compare each character to see if they match. A convenient way to reverse a string in Python is to use the slicing syntax string[::-1], which creates a new string that is the reverse of the original.
Given that we want to find the first palindromic string, we can use Python's next function combined with a generator expression to efficiently look for it. The generator expression creates an iterator that will only process each string as needed, which is both memory efficient and potentially time-saving if the palindromic string is found early in the array. The next function then tries to get the first element from this generator, and if none is found, it returns a default value, which in this case is the empty string "". This succinctly solves the problem without needing extra loops or conditionals to handle the case where no palindromic string is found.
Learn more about Two Pointers patterns.
A heap is a ...?
Solution Approach
The solution uses a generator expression that iterates over the list of words. This expression takes each word w in words and checks if it is a palindrome by comparing the word to its reverse, w[::-1]. This reversal is done using Python's slice notation, which, when provided with [::-1], starts from the end of the string and steps backwards, effectively reversing it.
Here's a step by step breakdown of the algorithm:
-
The generator expression
(w for w in words if w == w[::-1])creates an iterator. This iterator goes through each stringwin thewordsarray and yields it if and only if the string is the same as its reversed version. This leverages the fact that a palindrome is by definition a string that does not change when its characters are reversed. -
Python’s
nextfunction is used to retrieve the next item from the iterator created by the generator expression. In this context, it serves to fetch the first palindrome it encounters while iterating over the generator. -
The second argument to the
nextfunction is"", which is the default value to return in case the generator does not yield any items, i.e., if there are no palindromic strings in the array.
This solution is elegant and efficient:
- It avoids the need for an explicit loop to iterate over the elements and check them one by one.
- It uses lazy evaluation: the generator expression is only evaluated up to the point where the first palindrome is found, which can save time if a palindrome occurs early in the list.
- There's no need for additional memory to store intermediate results, as the generator doesn't create a temporary list of palindromes, unlike, for example, a list comprehension would.
Overall, the use of next and a generator expression allows for an efficient and concise solution to the problem.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Example Walkthrough
Let's go through a small example to illustrate the solution approach step by step. We have the following array of strings:
1words = ["hello", "world", "racecar", "level", "sample"]
We are looking to find the first string that is palindromic.
-
The first string we check is
"hello". We reverse it to see if it matches its original form: "olleh". Since"hello"is not equal to"olleh", we continue to the next word. -
The next string is
"world". Reversed, it is"dlrow", which again does not equal"world". So we move on. -
We come to
"racecar"and reverse it. The reversed version is"racecar"— it matches exactly! Since we found a palindrome, we don't need to check any further; we return"racecar".
To represent this process programmatically:
1# use generator expression to iterate over each word and check if it is a palindrome
2palindromic_string = next((w for w in words if w == w[::-1]), "")
3print(palindromic_string) # This will output "racecar"
The generator expression (w for w in words if w == w[::-1]) iterates through each word in the words array and yields the word if it is a palindrome. The next function is then used to get the first item from the iterator. If no palindromic string is found, it will return the default specified by the second argument, which is "".
In this example, the next function does not need to go through the entire list since it returns as soon as it finds the palindromic string "racecar". Thus, the generator stops iterating after the third element, demonstrating efficient use of resources. If racecar had not been a palindrome, the iteration would continue to "level", which is the next palindromic string, or until the list was exhausted.
Solution Implementation
1from typing import List # Import List from the typing module for type hinting
2
3class Solution:
4 def firstPalindrome(self, words: List[str]) -> str:
5 """
6 Finds the first palindromic word from a list of words.
7
8 Args:
9 words (List[str]): A list of strings.
10
11 Returns:
12 str: The first palindromic word in the list of words, or an
13 empty string if there is no such word.
14 """
15 # Iterate through each word in the list
16 for word in words:
17 # Check if the current word is the same as its reversed copy
18 if word == word[::-1]:
19 return word # Return the palindromic word
20
21 # Return an empty string if no palindromic word is found
22 return ""
23
24# Example usage:
25# sol = Solution()
26# print(sol.firstPalindrome(["abc", "car", "ada", "racecar", "cool"]))
27# This will print "ada" as it is the first palindrome in the list
281class Solution {
2 // This method finds the first palindromic string in an array.
3 public String firstPalindrome(String[] words) {
4 // Iterate over each word in the array.
5 for (String word : words) {
6 // Assume initially that each word could be a palindrome.
7 boolean isPalindrome = true;
8 // Use two pointers to compare characters from the front and the back.
9 for (int i = 0, j = word.length() - 1; i < j; ++i, --j) {
10 // If corresponding characters do not match, the word is not a palindrome.
11 if (word.charAt(i) != word.charAt(j)) {
12 isPalindrome = false;
13 // No need to check remaining characters if a mismatch is found.
14 break;
15 }
16 }
17 // If the word is a palindrome, return it.
18 if (isPalindrome) {
19 return word;
20 }
21 }
22 // Return an empty string if no palindromic strings are found.
23 return "";
24 }
25}
261#include <vector>
2#include <string>
3
4class Solution {
5public:
6 // Function to find the first palindrome in a list of words.
7 string firstPalindrome(vector<string>& words) {
8 // Iterate over each word in the vector.
9 for (const auto& word : words) {
10 // Assume initially that the word is a palindrome.
11 bool isPalindrome = true;
12
13 // Check each character from the start and the end of the word moving towards the center.
14 for (int start = 0, end = word.size() - 1; start < end; ++start, --end) {
15 // If the characters do not match, the word is not a palindrome.
16 if (word[start] != word[end]) {
17 isPalindrome = false;
18 break; // Exit the loop early as we already know it's not a palindrome.
19 }
20 }
21
22 // If the word is a palindrome, return it.
23 if (isPalindrome) {
24 return word;
25 }
26 }
27
28 // If no palindrome is found, return an empty string.
29 return "";
30 }
31};
321// This function searches for the first palindrome string within an array of words.
2// A palindrome is a word that reads the same backward as forward.
3// @param words - An array of strings to be checked.
4// @returns The first palindrome string if one exists, or an empty string if none is found.
5function firstPalindrome(words: string[]): string {
6 // Loop through each word in the array to check for palindromes.
7 for (const word of words) {
8 // Initialize pointers for the start and end of the word.
9 let startIndex = 0;
10 let endIndex = word.length - 1;
11
12 // Move the pointers towards the center of the word.
13 while (startIndex < endIndex) {
14 // Check if the characters at the start and end pointers do not match.
15 if (word[startIndex] !== word[endIndex]) {
16 // If they do not match, break from the loop; the word is not a palindrome.
17 break;
18 }
19 // Move the pointers closer to the center.
20 startIndex++;
21 endIndex--;
22 }
23
24 // If the pointers have met or crossed, the word is a palindrome.
25 if (startIndex >= endIndex) {
26 // Return the current palindrome word.
27 return word;
28 }
29 }
30
31 // If no palindrome is found in the array, return an empty string.
32 return '';
33}
34Depth first search is equivalent to which of the tree traversal order?
Time and Space Complexity
Time Complexity
The provided code checks each word in the list to see if it is a palindrome. The time it takes to check if a word is a palindrome depends on the length of the word, as it requires comparing characters from the beginning and the end towards the center.
To determine the time complexity, let n be the number of words in the list and k be the average length of these words.
Checking if a single word is a palindrome has a complexity of O(k) because we need to compare about half of the characters (in the worst case) to their counterparts on the other side of the word.
As we use a generator expression with the next function to find the first palindrome, the worst-case scenario happens when the palindrome is the last word in the list or there is no palindrome at all. Therefore, we might need to check every word. In this case, the time complexity would be O(n * k), as we perform an O(k) operation n times.
Space Complexity
The space complexity of the algorithm is O(1).
This is because it uses a constant amount of additional space regardless of the input size. The generator expression does not create an additional list in memory; it simply iterates over the existing list, and string slicing creates a new string, but since we are only interested in one word at a time, this does not accumulate with the number of words. Thus, the space used does not scale with the number of words n or their lengths k.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.