# 11-line Python solution, easy to understand, mix all words + all reversed words then use common prefix

• Sort all words and all reversed words. One word (call it A) is the prefix of the following words (call it B). If A is B's prefix and one is reversed one is not, and their indexes are different, then we find a palindrome pair.

def palindromePairs(self, words):
# 0 means the word is not reversed, 1 means the word is reversed
words, length, result = sorted([(w, 0, i, len(w)) for i, w in enumerate(words)] +
[(w[::-1], 1, i, len(w)) for i, w in enumerate(words)]), len(words) * 2, []
for i, (word1, rev1, ind1, len1) in enumerate(words):
for j in xrange(i + 1, length):
word2, rev2, ind2, _ = words[j]
if word2.startswith(word1):
if ind1 != ind2 and rev1 ^ rev2:
rest = word2[len1:]
if rest == rest[::-1]: result += ([ind1, ind2],) if rev2 else ([ind2, ind1],)
else:
break
return result

• This is an elegant solution. But the number of lines is not 11, should be around 15 because:
In line one, there is no semantic reason of combining words, length, and result in one line.
Similarly for the very long if if else...

• Right, I just want to make the code shorter. For result += ([ind1, ind2],) if rev2 else ([ind2, ind1],), I think it's more readable (like English) compared with if rev2: result += ([ind1, ind2],) else: result += ([ind2, ind1],) .

• however the complexity is O(n^2)

• Unfortunately yes

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.