318. Maximum Product of Word Lengths

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:

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.

解题要点：

用位运算符的方法，把array里每个单词都运算一遍存到新array里。然后遍历一遍原有数组每个数经过位运算的值拿来比较，如没有重合，则是两个不含对方字母的单词，记录最大长度的乘积。

class Solution {
    public int maxProduct(String[] words) {
        if(words == null && words.length == 0) return 0;
        int n = words.length;
        int[] value = new int[n];
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < words[i].length(); j++){
                value[i] |= 1 << (words[i].charAt(j) - 'a');
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if((value[i] & value[j]) == 0){
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}