Maximum Product of Word Lengths

此题实际上就是要用bitmap来实现缩减在字符串比对上消耗的时间，这里自己的做法是用了真bitmap也就是26长度的bool数组，这种方法相当于对每两个字符的对比时间是O(26)实际上也就是O(1)了，但是时间常数大，不过作为清晰解释了题目原理的代码很适合拿来具体解释方法

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        n = len(words)
        store = {}
        bitMap = [[False] * 26 for _ in xrange(n)]
        for index, word in enumerate(words):
            tmp = set(word)
            store[index] = tmp
            self.setBitMap(tmp, index, bitMap)

        result = 0
        for i in xrange(n):
            for j in xrange(i + 1, n):
                if self.check(i, j, store, bitMap):
                    result = max(result, len(words[i]) * len(words[j]))        

        return result

    def setBitMap(self, charSet, index, bitMap):
        for char in charSet:
            bitMap[index][ord(char) - ord('a')] = True

    def check(self, i, j, store, bitMap):
        setI, setJ = store[i], store[j]
        checkSet = setI if len(setI) < len(setJ) else setJ

        for char in checkSet:
            if bitMap[i][ord(char) - ord('a')] and bitMap[j][ord(char) - ord('a')]:
                return False
        return True

下面这种方法就比较神了，我们可以利用2的26次方范围内的数，一个bit表示一个字母的方法来存储一个字符串拥有的字母信息，这样我们就不要真正的bitmap而只需要一个数字了，比较的时间进一步由O(26)变成真正的O(1)了

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        store = {}
        for index, word in enumerate(words):
            bitMap = 0
            for char in set(word):
                bitMap |= 1 << (ord(char) - ord('a'))
            store[index] = bitMap

        result = 0
        for i in xrange(len(words)):
            for j in xrange(i + 1, len(words)):
                if store[i] & store[j] == 0:
                    result = max(result, len(words[i]) * len(words[j]))

        return result