318. 最大单词长度乘积

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
示例 2:

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。
示例 3:

输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。

本题其实思路很简单，就是每个单词进行比较，第一个单词和后面的每个单词进行比较，是否有重复单词，如果没有就算长度乘积，然后一直遍历到最后即可。
关键是如何比较的问题，我们这里可以用位运算，一共26个字母，我们就0-25个1，通过位运算来辨别是否用相同字母只需要O(1)的复杂度，如果用暴力算的话复杂度就会很高。
代码如下:

class Solution {
    public int maxProduct(String[] words) {
        
        int n = words.length;
        int[] mask = new int[n];

        for(int i = 0; i < n; i++){
            int bit = 0;
            for (int j = 0; j < words[i].length();j++){
                int b =   1 << (int)(words[i].charAt(j) - 'a') ;
                bit |=  b;
            }
            mask[i] = bit;
        }

        int max = 0;
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                if ( (mask[i] & mask[j]) == 0){
                    int len = words[i].length() * words[j].length();
                    if (len > max) 
                        max = len;
                }
            }
        }
        return max;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-of-word-lengths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。