336. Palindrome Pairs

Description

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

• 0 <= i, j < words.length,
• i != j, and
• words[i] + words[j] (the concatenation of the two strings) is a
  palindrome
  .

Return an array of all the palindrome pairs of words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.

 

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

Example 2:

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]

 

Constraints:

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lowercase English letters.

 

Solutions

Solution: Hash Map

• Time complexity: O(n*words[i].length²)
• Space complexity: O(n*words[i].length)

 

JavaScript

/**
 * @param {string[]} words
 * @return {number[][]}
 */
const palindromePairs = function (words) {
  const wordMap = new Map();
  const wordSizeSet = new Set();
  const isPalindrome = (word, left, right) => {
    while (left < right) {
      if (word[left] !== word[right]) return false;
      left += 1;
      right -= 1;
    }
    return true;
  };
  const result = [];

  for (const [index, word] of words.entries()) {

    wordMap.set(word, index);
    wordSizeSet.add(word.length);
  }
  for (const [index, word] of words.entries()) {
    const size = word.length;
    const reverseWord = word.split('').reverse().join('');
    const reverseWordIndex = wordMap.get(reverseWord);

    if (reverseWordIndex !== undefined && reverseWordIndex !== index) {
      result.push([index, reverseWordIndex]);
    }
    for (let length = 0; length < size; length++) {
      if (!wordSizeSet.has(length)) continue;
      if (isPalindrome(reverseWord, 0, size - length - 1)) {
        const subWord = reverseWord.slice(size - length);

        if (wordMap.has(subWord)) {
          result.push([index, wordMap.get(subWord)]);
        }
      }
      if (isPalindrome(reverseWord, length, size - 1)) {
        const subWord = reverseWord.slice(0, length);

        if (wordMap.has(subWord)) {
          result.push([wordMap.get(subWord), index]);
        }
      }
    }
  }
  return result;
};