Palindrome Word Pairs
HardArrays & Hashing
Problem
A word-art installation glues two word tiles side by side, and the result is displayed only if it reads the same forwards and backwards.
Given a list of distinct lowercase words, return the number of ordered pairs (i, j) with i ≠ j such that words[i] + words[j] is a palindrome.
Example 1
- Input:
- words = ["ab", "ba", "aba", "c"]
- Output:
- 4
"ab"+"ba" = "abba", "ba"+"ab" = "baab", "aba"+"ba" = "ababa" and "ab"+"aba" = "ababa".
Example 2
- Input:
- words = ["race", "car", "ecar", ""]
- Output:
- 3
"racecar", "raceecar" and "ecarrace". The empty word pairs only with palindromes, and there are none.
Constraints
- 1 ≤ words.length ≤ 5000
- 0 ≤ words[i].length ≤ 300
- Words are distinct and contain only lowercase English letters.
Hint
Show the first hint
Checking all n² concatenations costs n² · L. Fix one word and ask what its partner must look like.
Walkthrough
How to approach it
01Clarify before coding
- Are pairs ordered? Yes, (i, j) and (j, i) are different and both may count.
- Can a word pair with itself? No, i ≠ j.
- Can the empty string appear? Yes, at most once since words are distinct; it pairs with every palindrome in both orders.
02Brute force
Concatenate every ordered pair and test whether the result is a palindrome.
Cost: O(n² · L) time: 2.5·10^7 pairs × 600 characters ≈ 1.5·10^10 for the limits.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.