prefixes = defaultdict(list)
for w in words:
    prefixes[w[1::-1]].append(w)
pairs = set(frozenset((w1, w2)) for w1 in words for w2 in prefixes[w1[1:]])
Использование Regex для поиска пар слов из списка слов