Palindrome Pairs

palindrome_pairs.py

"""
Description:
Given a list of unique words, find all pairs of distinct indices (i, j) in the given
list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Examples:
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
parlindromes are: ["dcbaabcd","abcddcba","slls","llssssll"]

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

def palindromePairs(words):
    """
    :type words: List[str]
    :rtype: List[List[int]]
    """
    result = []
    revIndex = {w[::-1]: i for i, w in enumerate(words)}
    for i in range(len(words)):
        word = words[i]
        for j in range(len(word)+1):
            prefix, suffix = word[:j], word[j:]
            if prefix in revIndex and\
                revIndex[prefix] != i and\
                suffix == suffix[::-1]:
                result.append([i, revIndex[prefix]])
            if j > 0 and suffix in revIndex and\
                revIndex[suffix] != i and\
                prefix == prefix[::-1]:
                result.append([revIndex[suffix], i])
    return result