Palindrome Pairs

这个题不能被tag带到笼子里去了，其实这里的方法和暴力法是差不了多少的，唯一有点巧妙的是根据字符串长度存了一个哈希表，这个哈希表让我们可以比较快速的对比那种两个词拼起来构成对称字符串的情况，这里最主要需要注意空字符串这种情况，空串必须单独拿出来处理

class Solution(object):
    def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        result = []
        indexMap = {word : index for index, word in enumerate(words)}
        lengthMap = collections.defaultdict(set)
        for word in words:
            lengthMap[len(word)].add(word)

        for index, word in enumerate(words):
            revWord = word[::-1]
            n = len(revWord)
            for i in xrange(n):
                if i == 0 and '' in lengthMap[0]:
                    if revWord == word:
                        result.append([index, indexMap['']])
                        result.append([indexMap[''], index])
                        continue
                if revWord[:i] in lengthMap[i] and indexMap[revWord[:i]] != index:
                    if self.isPalindrome(revWord, i, n):
                        result.append([indexMap[revWord[:i]], index])
                if revWord[i:] in lengthMap[n - i] and indexMap[revWord[i:]] != index:
                    if self.isPalindrome(revWord, 0, i):
                        result.append([index, indexMap[revWord[i:]]])

        return result

    def isPalindrome(self, string, start, end):
        left, right = start, end - 1
        while left <= right:
            if string[left] != string[right]:
                return False
            left += 1
            right -= 1
        return True