# 318. Maximum Product of Word Lengths

[**318. Maximum Product of Word Lengths**](https://leetcode.com/problems/maximum-product-of-word-lengths/)

Given a string array `words`, return *the maximum value of* `length(word[i]) * length(word[j])` *where the two words do not share common letters*. If no such two words exist, return `0`.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

* `2 <= words.length <= 1000`
* `1 <= words[i].length <= 1000`
* `words[i]` consists only of lowercase English letters.

***My Solutions:***

用了一个int整数表示一个单词中每种字母出现与否。用0代表该字母没有出现过，1代表出现过，因此一个单词中所有字母出现的情况可以使用一组01的二进制数字来表示。比如abz，可以表示为11000…0001（中间省略的都是0）&#x20;

对于任意两个单词，只要将他们的状态进行并运算（&），如果结果是0，代表他们没有相同字母，即可以进行乘积。

```
class Solution {
        
        for (int i = 0; i < len; i++) {
            
            // build the bitmap for each word
            char[] chars = words[i].toCharArray();
            int bit = 0;
            for (char c : chars) {
                // a SHL b表示把，高位丢a转为二进制后左移b位（在后面添b个0）弃，低位补0。
                // 比如0变成1,1变成10,2变成100。。。
                // 这里的结果是，离a越远的数字，mask越大，比如abz，最终会表示为1000...0011
                bit |= 1 << (c - 'a');
            }
            bitmap[i] = bit;
            
            for (int j = 0; j < i; j++) {
                if ((bitmap[i] & bitmap[j]) == 0) // no common set bit
                    max = Math.max(max, words[i].length() * words[j].length());
            }
        }
        
        return max;
    }
}
```
