Palindrome Pairs | Problems

Given a list of unique words, find all pairs (i,j) such that words[i]+words[j] is a palindrome.

Example: words = ["abcd","dcba","lls","s","sssll"] → [[0,1],[1,0],[3,2],[2,4]]

Sample Input

—

Sample Output

—

Constraints

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

Topics

Tries

Trie / Hash Map

function palindromePairs(words) {
  const map = new Map(); words.forEach((w,i) => map.set(w, i));
  const isPalin = s => { let l=0,r=s.length-1; while(l<r) if(s[l++]!==s[r--]) return false; return true; };
  const result = [];
  for (let i = 0; i < words.length; i++) {
    const w = words[i];
    for (let j = 0; j <= w.length; j++) {
      const left = w.slice(0,j), right = w.slice(j);
      const revLeft = left.split('').reverse().join('');
      const revRight = right.split('').reverse().join('');
      if (isPalin(right) && map.has(revLeft) && map.get(revLeft)!==i) result.push([i, map.get(revLeft)]);
      if (j > 0 && isPalin(left) && map.has(revRight) && map.get(revRight)!==i) result.push([map.get(revRight), i]);
    }
  }
  return result;
}

Time: O(n × k²) | Space: O(n × k)

Saved in this browser only. Private to you.