Show problems as
Classic problem #336HardArrayHash TableStringTrieHash Function

Palindrome Pairs

Real-world version: Pairs of Labels That Read the Same Both Ways
Tracked in this browser only
Read Palindrome Pairs on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Labels are given as labels, each a string of lowercase letters. A label may be empty, and two labels may read alike while sitting at different positions in the list.

Return every ordered pair of positions [i, j] with i and j different, such that the label at i written straight before the label at j, with nothing between them, reads the same backwards as forwards.

List the pairs in increasing order, comparing the first position and, where those match, the second.

Examples

Example 1

Input
labels = ["ab", "ba"]
Output
[[0, 1], [1, 0]]

Either way round the two labels join into a four-letter string that reads the same backwards, so both orderings count.

Example 2

Input
labels = ["race", "ecar", "car", "rac"]
Output
[[0, 1], [0, 2], [1, 0], [2, 3], [3, 1], [3, 2]]

Six joins work. Position 0 goes before positions 1 and 2, position 1 goes before position 0, position 2 goes before position 3, and position 3 goes before positions 1 and 2. Position 0 before position 3 fails: that join runs to seven letters and its two ends do not answer each other.

Example 3

Input
labels = ["ab", "cd"]
Output
[]

Neither ordering of the two labels reads the same backwards, so nothing is reported.

Constraints

  • 1 <= labels.length <= 5000
  • 0 <= labels[i].length <= 300
  • Every label is made of lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def palindrome_pairs(labels: list[str]) -> list[list[int]]:
Java
public List<List<Integer>> palindromePairs(String[] labels)

More on the same topics