Leetcode problem 94 - Find First Palindromic String in the Array

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.

/**
 * @param {string[]} words
 * @return {string}
 */
var firstPalindrome = function (words) {
  // Iterate through each word in the array
  for (let i = 0; i < words.length; i++) {
    // reversedWord = words[i].split("").reverse().join("");

    // Split the current word into an array of characters
    let wordArr = words[i].split("");

    // Initialize two pointers for reversing the characters in the word
    let left = 0;
    let right = wordArr.length - 1;

    // Use a while loop to reverse the characters in the current word
    while (left < right) {
      // Swap characters at 'left' and 'right' positions using a temporary variable
      let temp = wordArr[left];
      wordArr[left] = wordArr[right];
      wordArr[right] = temp;

      // Increment 'left' and decrement 'right' pointers
      left++;
      right--;
    }

    // if (words[i] == reversedWord) {

    // Join the reversed characters back into a word
    // Check if the reversed word is equal to the original word
    if (words[i] == wordArr.join("")) {
      // Return the word if it is a palindrome
      return words[i];
    }
  }
  // Return an empty string if no palindrome is found
  return "";
};

Time Complexity:

The time complexity of the code is O(n * m), where n is the number of words in the array (words), and m is the maximum length of any word in the array.

Space Complexity: The space complexity is O(n), where n is the maximum length of any word in the array. The additional space is used to store the character array (wordArr) for each word.