Skip to content

336. Palindrome Pairs

Difficulty Topics

Description

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 string.

Return an array of all the palindrome pairs of words.

 

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"]

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]

 

Constraints:

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

Solution

palindrome-pairs.py
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        N = len(words)
        mp = {x : i for i, x in enumerate(words)}
        res = []

        for index, word in enumerate(words):
            for j in range(len(word) + 1):
                prefix = word[:j]
                suffix = word[j:]

                if prefix == prefix[::-1]:
                    suffixR = suffix[::-1]
                    if word != suffixR and suffixR in mp:
                        res.append([mp[suffixR], index])

                if j != len(word) and suffix == suffix[::-1]:
                    prefixR = prefix[::-1]
                    if word != prefixR and prefixR in mp:
                        res.append([index, mp[prefixR]])

        return res