Palindrome Pairs Hard 0 attempts
LeetCode ↗

Palindrome Pairs

Hard Tries LeetCode

You're given a list of distinct words. Find every pair of indices (i, j) — where i and j are different — such that joining words[i] and words[j] together produces a palindrome.

Input Format
Implement palindromePairs(words). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

Input
words = ["abcd","dcba","lls","s","sssll"]
Output
[[0,1],[1,0],[3,2],[2,4]]

Example 2

Input
words = ["a",""]
Output
[[0,1],[1,0]]
Constraints
  • 1 <= words.length <= 5000
  • 0 <= words[i].length <= 300
  • words[i] consists of lowercase English letters
Test Cases (2)
Case 1
Args: [["abcd","dcba","lls","s","sssll"]] Expected: [[0,1],[1,0],[3,2],[2,4]]
Case 2
Args: [["a",""]] Expected: [[0,1],[1,0]]
Topics
Tries

Hash Map of Reversed Split Candidates

javascript
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.

JavaScript