# O(n * m^2) simple Python solution with explanation

• ``````    def palindromePairs(self, words):
"""
:type words: List[str]
:rtype: List[List[int]]
"""
# return prefix, suffix of a word, 'abc' -> ['','abc'], ['a','bc']..['abc','']
def partition_word(word): # O(m) time where m is length of word, O(1) space with generator
for i in xrange(len(word)+1):
yield word[:i], word[i:]

def isPalindrome(word): # O(m/2) time, O(1) space
if not word: return False
pos = (len(word)-len(word)%2)/2
for i in xrange(pos):
if word[i] != word[-1-i]:
return False
return True

match = []
# Create table with word as key and index as value, O(n) space
words_table = dict((word, i) for i, word in enumerate(words))

for word, i in words_table.items(): # O(n * m^2)
# Handle single case for non-palindromic word
# 'abc' + {'cba'}
if len(word) > 1 and not isPalindrome(word) and word[::-1] in words_table:
match.append([i, words_table[word[::-1]]])

for prefix, suffix in partition_word(word): # O(m * m)
# {'cba'} + palindrome + 'abc'
# {''} + palindrome + ''
if isPalindrome(prefix) and suffix[::-1] in words_table:
match.append([words_table[suffix[::-1]], i])
# 'abc' + palindrome + {'cba'}
# '' + palindrome + {''}
if isPalindrome(suffix) and prefix[::-1] in words_table:
match.append([i, words_table[prefix[::-1]]])

return match``````

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