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.

思路

我们需要找出字符串数组中，两个没有重复字符的字符串，并且它们的乘积要最大。

我们当然需要统计数组中每一个字符串，字母出现的次数。但是用什么方法来统计呢？如果用哈希表，空间复杂度可能会有点高，毕竟我们只有确定的26个字母。我选择利用alphabet[26]，来存储字母次数的统计量。

其实还有更有技巧的方法，可以把字母统计量用位操作的方式存储在整数当中。利用移位运算给整数的相应位数赋上相应的值即可。

接下来，我们将数组里的数的对应长度，两两相乘；如果不满足题意，就不考虑这个乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import copy
class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        stats = []
        alphabet = []
        lens = []
        length = len(words)
        for i in range(26):
            alphabet.append(0)
            
        for i in range(length):
            tmp = copy.copy(alphabet)
            stats.append(tmp)
            
        for i, word in enumerate(words):
            for s in word:
                stats[i][ord(s)-ord("a")] += 1
            lens.append(len(word))
        
        product = 0
        for i in range(length):
            for j in range(i+1,length):
                duplicate = False
                for k in range(26):
                    if (stats[i][k] and stats[j][k]):
                        duplicate = True
                        break
                
                if (duplicate):
                    continue
                else:
                    tmpproduct = lens[i] * lens[j]
                    if (tmpproduct > product):
                        product = tmpproduct
        
        return product