318. Maximum Product of Word Lengths

318. 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）

对于任意两个单词，只要将他们的状态进行并运算（&），如果结果是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;
    }
}