1.题目

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0。

示例 1：
输入：words = [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
输出：16
解释：这两个单词为 “abcw”, “xtfn”。

示例 2：
输入：words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
输出：4
解释：这两个单词为 “ab”, “cd”。

示例 3：
输入：words = [“a”,“aa”,“aaa”,“aaaa”]
输出：0
解释：不存在这样的两个单词。

提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-product-of-word-lengths

2.思路

（1）暴力穷举法
暴力穷举法比较容易想到，具体步骤如下：
① 先创建函数 hasCommonLetter(word1, word2)，其用与判断单词 word1 和 word2 是否含有公共字母，如果有返回 true，否则返回 false；

public boolean hasCommonLetter(String word1, String word2);

② 使用 2 层 for 循环来枚举所有的 words[i] 和 words[j]，并且使用函数 hasCommonLetter 来判断它们是否含有公共字母，如果没有，则用变量 res 来保存 length(words[i]) * length(words[j]) 的最大值；
③ 遍历结束后，直接返回 res 即可。

不过该方法的时间复杂度较高，在 LeetCode 上提交时会出现“超出时间限制”的提示！

（2）位运算 & 状态压缩
思路参考该 LeetCode 用户题解。

① 定义长度为 words.length 的数组 masks，其中 masks[i] 的二进制表示的低 26 位（从右往左）分别代指单词 words[i] 中小写字母 a - z 是否出现过，这里为了方便理解，可看下面的例子：

例如，masks[1] = 131，131 = 128 + 2 + 1 的二进制表示为 0000 0000 0000 0000 0000 0000 1000 0011
而低 26 位（从右往左）分别指代小写字母 a - z 是否出现过，为 1 说明出现过，为 0 则说明没有出现
那么 masks[1] = 131 说明单词 words[0] 中出现了小写字母 a、b 和 h

看到这里，可能有读者会问，数组 masks 的作用是什么呢？其主要作用在于判断单词 words[i] 和 words[j] 是否含有公共字母。

例如，words[0] = "abc"，words[1] = "bafd"，那么对应的 
masks[0] = 0000 0000 0000 0000 0000 0000 0111 = 7，
masks[1] = 0000 0000 0000 0000 0000 0010 1011 = 43
此时进行如下与运算：masks[0] & masks[1] = 0000 0000 0000 0000 0000 0000 0011 = 3 != 0，
那么便可以说明单词 words[i] 和 words[j] 含有公共字母；反之，如果 masks[0] & masks[1] = 0，那么说明它们不含有公共字母。

其背后的原理在于，如果 words[i] 和 words[j] 含有公共字母（假设是字母 ‘a’），那么它们对应的 masks[i] 和 masks[j] 的二进制表示的最低位必然均为 1，此时 masks[i] 和 masks[j] 相与的结果自然不可能为 0（因为最低位的结果必为 1），所以根据这一点便可以进行判断。

② 有了数组 masks 之后，后面就只需要使用 2 层 for 循环来枚举不含有公共字母的 (words[i], words[j]) ，同时使用变量 res 来记录 words[i].length() * words[j].length() 的最大值；

③ 当遍历结束后，直接返回 res 即可。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public int maxProduct(String[] words) {
        int length = words.length;
        int res = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (!hasCommonLetter(words[i], words[j])) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
    
    //判断单词 word1 和 word2 是否含有公共字母
    public boolean hasCommonLetter(String word1, String word2) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            cnt1[word1.charAt(i) - 'a']++;
        }
        for (int i = 0; i < word2.length(); i++) {
            cnt2[word2.charAt(i) - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] != 0 && cnt2[i] != 0) {
                return true;
            }
        }
        return false;
    }
}

//思路2————位运算 & 状态压缩
class Solution {
    public static int maxProduct(String[] words) {
        int length = words.length;
        int index = 0;
        /*
            masks[i] 的二进制表示的低 26 位(从右往左)分别代指单词 words[i] 中小写字母 a - z 是否出现过
            例如，masks[0] = 129，129 的二进制表示为 0000 0000 0000 0000 0000 0000 1000 0001
            那么说明单词 words[0] 中出现了小写字母 a 和 h
        */
        int[] masks = new int[length];
        for (String word : words) {
            int t = 0;
            for (int i = 0; i < word.length(); i++) {
                int c = word.charAt(i) - 'a';
                t |= (1 << c);
            }
            masks[index++] = t;
        }
        int res = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < i; j++) {
                //(masks[i] & masks[j]) == 0 说明 words[i] 和 words[j] 不含有公共字母
                if ((masks[i] & masks[j]) == 0) {
                    //更新 res
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}