8.19 - hard - 70

336. Palindrome Pairs

基本想出来是怎么做，只是一上来就想去优化，结果想的有点乱，其实最好的方法是先去实验双层循环，然后再去想着优化（利用hash），一开始就去想实在太乱了。

class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        d, res = dict([(w[::-1], i) for i, w in enumerate(words)]), []

        for i, w in enumerate(words):
            # 对于每一个word
            for j in xrange(len(w)+1):
                prefix, postfix = w[:j], w[j:]
                # 情况1：prefix存在，比如说 abcdad 如果abc存在于d里也就是cba存在，而且dad是valid
                if prefix in d and i != d[prefix] and postfix == postfix[::-1]:
                    res.append([i, d[prefix]])
                # 情况2: 后缀在d里，比如说abacde cde在d里，也就是edc存在，然后前缀是循环的
                if j>0 and postfix in d and i != d[postfix] and prefix == prefix[::-1]:
                    res.append([d[postfix], i])
        return res