# Maximum Product of Word Lengths

## Problem

Given a string array `words`, find the maximum value of `length(words[i]) * length(words[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:

``````Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
``````

Example 2:

``````Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
``````

Example 3:

``````Input: ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.
``````

## Solution

### 集合暴力法

#### 代码

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````class Solution: def maxProduct(self, words): """ :type words: List[str] :rtype: int """ max = 0 set_words = [set(list(w)) for w in words] for i,word_1 in enumerate(words): for j,word_2 in list(enumerate(words))[i+1:]: if not (set_words[i] & set_words[j]): l = len(word_1)*len(word_2) max = l if l>max else max return max ``````

#### 评价

1. 使用集合虽然方便但集合运算耗时还是有的（对比与下面的位位运算
2. 在找最大值时没有好好利用Python自带的库函数和语法糖（自己写的就是比它慢！）

#### 代码

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````class Solution: def maxProduct(self, words): """ :type words: List[str] :rtype: int """ masks = {} start = ord('a') for w in words: mask = 0 for c in set(w): mask|=(1<

Single Number