Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]

Return 16

The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]

Return 4

The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]

Return 0

No such pair of words.

 

此题如果用暴力比较法，也就是两层循环依次比较的话，执行会超时。

可以通过类似C++中bitset的方法来保存每个单词的一个key值，然后直接用key值进行比较，减少单词之间比较的时候比较字符的时间。

比如单词abcw，我们可以创建一个l = [0,0,0.....0] 有27个0的数组，并按26个字母的顺序依次给a-z索引为1~26，最后把a,b,c,w四位对应的元素的值置为1，计算 pow(2,1)+pow(2,2)+pow(2,3)+pow(2,23)的和即为这个元素的key值。

再用这个key值与其他元素的key值做与操作，结果为0，则表示单词无相同的字符。

下面是代码：

 

class Solution(object):    index = []    def transChar(self,c):        l = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']        return l.index(c) + 1    def parseWords(self,w):        t = 0        l = []        for i in range(27):            l.append(0)        for i in set(w): #注：这里用set过滤掉相同的字符，我最初直接用w，导致运行超时            t = self.transChar(i)            l[t] = 1        t = 0        for i in range(len(l)):            if l[i] == 1:                t = t + pow(2,i)        #print w,t        return t    def maxProduct(self, words):        """        :type words: List[str]        :rtype: int        """        max = 0        if len(words) == 0:            return 0        l = []        for i in words:            l.append(self.parseWords(i))        for i in range(len(l)):            for j in range(i+1,len(l)):                if l[i] & l[j] == 0:                    if max < len(words[i]) * len(words[j]):                        max = len(words[i]) * len(words[j])        return max