Skip to main content

Palindrome Pairs

Problem Statement​

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

  • 0 <= i, j < word.length,
  • i != j, and
  • words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

Leetcode Link

Example 1:​

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

Example 2:​

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

Constraints:​

  • 1 <= words.length <= 5000
  • 0 <= words[i].length <= 300
  • words[i] consists of lowercase English letters.

Code​

Python
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        backward, res = {}, []
        for i, word in enumerate(words):
            backward[word[::-1]] = i

        for i, word in enumerate(words):

            if word in backward and backward[word] != i:
                res.append([i, backward[word]])

            if word != "" and "" in backward and word == word[::-1]:
                res.append([i, backward[""]])
                res.append([backward[""], i])

            for j in range(len(word)):
                if word[j:] in backward and word[:j] == word[j-1::-1]:
                    res.append([backward[word[j:]], i])
                if word[:j] in backward and word[j:] == word[:j-1:-1]:
                    res.append([i, backward[word[:j]]])

        return res