algoadvance

Leetcode 2108. Find First Palindromic String in the Array

Problem Statement

You are given an array of strings words. Your task is to find the first palindromic string in the array. A string is called a palindrome if it reads the same forward and backward. If there is no such string, return an empty string "".

Clarifying Questions

  1. Q: What should be returned if the input array is empty?
    • A: Return an empty string "".
  2. Q: Are the strings in the array always lower case?
    • A: Yes, for the purpose of this problem, the strings can be considered to be in lower case.
  3. Q: How do I handle strings with mixed or upper-case letters?
    • A: Assume all strings are in lower case.

Strategy

  1. Iterate through the array: Start from the first element and check each string.
  2. Check if each string is a palindrome: For each string, compare the characters from the beginning and the end towards the center.
  3. Return the first palindromic string: If a palindrome is found, return it immediately. If no palindrome is found by the end of the loop, return an empty string.

Code

Here’s a possible implementation in Java to achieve the solution:

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

    private boolean isPalindrome(String word) {
        int left = 0;
        int right = word.length() - 1;
        while (left < right) {
            if (word.charAt(left) != word.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // Driver code to test the solution
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] words = {"abc", "car", "ada", "racecar", "cool"};
        System.out.println(solution.firstPalindrome(words)); // Output: "ada"
    }
}

Time Complexity

Therefore, the total time complexity is O(m * L), where L is the maximum length of any string in the array. This ensures that our solution is efficient even for relatively large arrays of strings.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI