Palindrome Pairs — LeetCode 336 Python Solution

The problem

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 < words.length, i != j, and words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Example

Input

words = ["abcd","dcba","lls","s","sssll"]

Output

[[0,1],[1,0],[3,2],[2,4]]

Explanation

The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

Python solution

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        d = {w: i for i, w in enumerate(words)}
        ans = []
        for i, w in enumerate(words):
            for j in range(len(w) + 1):
                a, b = w[:j], w[j:]
                ra, rb = a[::-1], b[::-1]
                if ra in d and d[ra] != i and b == rb:
                    ans.append([i, d[ra]])
                if j and rb in d and d[rb] != i and a == ra:
                    ans.append([d[rb], i])
        return ans

Complexity

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 336. Palindrome Pairs is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Related problems