hardTriesPure DSA~45 min
Find All Palindrome-Forming Word Pairs
Given a dictionary of distinct words, find every ordered pair whose concatenation reads the same forwards and backwards — useful for detecting reversible token combinations.
Problem
Given a list of distinct words, return all index pairs (i, j), i != j, such that words[i] + words[j] is a palindrome.
Input
A list of distinct lowercase strings words.
Output
A list of [i, j] index pairs whose concatenation is a palindrome.
Constraints
- 1 ≤ words.length ≤ 5000
- 0 ≤ words[i].length ≤ 300
- Words are distinct, lowercase English.
- Sum of lengths ≤ 1e6.
Examples
Example 1
Input
["abcd","dcba","lls","s","sssll"]
Output
[[0,1],[1,0],[3,2],[2,4]]
'abcddcba', 'dcbaabcd', 'slls', 'llssssll' are palindromes.
Example 2
Input
["bat","tab","cat"]
Output
[[0,1],[1,0]]
'battab' and 'tabbat' are palindromes.