# Python O(n*avg_len^2) Solution

• ``````class Solution(object):
def isPalindrome(self, s):
for i in xrange(len(s)/2):
if (s[i] != s[len(s)-1-i]): return False
return True

def palindromePairs(self, words):
res = []
if not words: return res

# Hash the indices
n = len(words)
idx = {words[i] : i for i in xrange(n)}

for word in words:
for i in xrange(len(word)):
prefix, rprefix = word[:i], word[:i][::-1]
suffix, rsuffix = word[i:], word[i:][::-1]
if self.isPalindrome(prefix) and (rsuffix in idx) and idx[rsuffix] != idx[word]:
res.append([idx[rsuffix], idx[word]])
if self.isPalindrome(suffix) and (rprefix in idx) and idx[rprefix] != idx[word]:
res.append([idx[word], idx[rprefix]])
if not rprefix : res.append([idx[rprefix], idx[word]]) # deal with empty string
return res``````

• nice solution. Your complexity analysis is based on assumption that "rsuffix in idx" is always O(1) which is not very solid, although mostly true. Changing your isPalindrome(s) check to : return s == s[::-1] will save 1/3 - 1/4 time.

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