283. Palindrome Pairs
You are given an array words of distinct strings. An ordered pair of indices (i, j) is a palindrome pair if i != j and the concatenation words[i] + words[j] reads the same forwards and backwards.
Return every palindrome pair as a list of (i, j) index pairs, sorted by i ascending, ties broken by j ascending. Note that (i, j) and (j, i) are different pairs — gluing the two words in the other order produces a different string, which may or may not be a palindrome.
The empty string may appear in words; concatenating it with any word that is already a palindrome forms a palindrome pair in both orders.
Example 1:
Input: words = ["bat", "tab", "cat"]
Output: [[0, 1], [1, 0]]
Explanation: "bat" + "tab" = "battab" and "tab" + "bat" = "tabbat" are both palindromes. No pair involving "cat" works.
Example 2:
Input: words = ["abcd", "dcba", "lls", "s", "sssll"]
Output: [[0, 1], [1, 0], [2, 4], [3, 2]]
Explanation: "abcddcba", "dcbaabcd", "llssssll" (2 then 4), and "slls" (3 then 2) are all palindromes.
Constraints:
- 1 ≤ words.length ≤ 500
- 0 ≤ words[i].length ≤ 100
- The total number of characters across all words is at most 10⁵.
- words[i] consists of lowercase English letters only.
- All words are distinct.
Hints:
The direct route is to test every ordered pair (i, j) with a palindrome check on the glued string — that's O(n² · k) and a good correctness baseline, but too slow when n is large.
Flip the question: instead of asking "which partners work with words[i]?", derive what a partner must look like. Cut words[i] into prefix + suffix at every split point. If the prefix is itself a palindrome, then partner + words[i] is a palindrome exactly when partner is the reverse of the suffix. Symmetrically, if the suffix is a palindrome, words[i] + partner works when partner is the reverse of the prefix.
Store every word's index in a hash map keyed by the word. For each word do k+1 splits, look up the reversed half in O(1) (hash) or O(length) (trie), and skip cut = len(word) in the suffix branch so the exact-reverse pair isn't reported twice.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["bat", "tab", "cat"]
Expected output: [[0, 1], [1, 0]]