剑指 Offer II 005. 单词长度的最大乘积（Java）

题目：

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

示例 1:

示例 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/aseY1I
 

思路：

解法一、暴力

        为了得到单词长度的最大乘积，朴素的做法是，遍历字符串数组 words 中的每一对单词，判断这一对单词是否有公共字母，如果没有公共字母，则用这一对单词的长度乘积更新单词长度的最大乘积。

        时间复杂度为O(∑0≤i<j<n li×lj) > O(n^2)，需要 O(li​×lj​) 的时间判断是否有公共字母和计算长度乘积。

解法二、位运算【是否有公共字母---字母掩码按位与运算】

        如果可以将判断两个单词是否有公共字母的时间复杂度降低到 O(1)，则可以将总时间复杂度降低到 O(n^2)。

        可以使用位运算预处理每个单词，通过位运算操作判断两个单词是否有公共字母。由于单词只包含小写字母，共有 26 个小写字母，因此可以使用位掩码的最低 26 位分别表示每个字母是否在这个单词中出现。将 a 到 z 分别记为第 0 个字母到第 25 个字母，则位掩码的从低到高的第 i 位是1当且仅当第 i 个字母在这个单词中，其中 0≤i≤25。

        用数组 masks 记录每个单词的位掩码表示。计算数组 masks 之后，判断第 i 个单词和第 j 个单词是否有公共字母可以通过判断 masks[i] & masks[j] 是否等于0 实现，当且仅当masks[i] & masks[j]=0 时第 i 个单词和第 j 个单词没有公共字母，此时使用这两个单词的长度乘积更新单词长度的最大乘积。

        时间复杂度：O(L+n^2)（ L 是数组 wordswords 中的全部单词长度之和，n 是数组words 的长度）；空间复杂度：O(n)，需要创建长度为 n 的位掩码数组 masks。

执行用时：6 ms, 在所有 Java 提交中击败了99.67%的用户

内存消耗：41.4 MB, 在所有 Java 提交中击败了58.23%的用户

class Solution {
    public int maxProduct(String[] words) {
        int len = words.length;
        int[] masks = new int[len];
        //对每个单词进行字母掩码预处理
        for(int i = 0; i < len; i++){
            String word = words[i];
            int wordLen = word.length();
            //位掩码的第j位是1当且仅当第 j 个字母在这个单词中
            for(int j = 0; j < wordLen; j++){
                masks[i] |= 1 << (word.charAt(j) - 'a'); //填1用或运算，减'a'表示第几个字母（1的左移量）
            }
        }
        int ans = 0;
        for (int i = 0; i < len; i++){
            for(int j = i + 1; j < len; j++){
                //无公共字母后更新最大乘积
                if((masks[i] & masks[j]) == 0){
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }
        return ans;
    }
}

解法三、位运算优化【哈希映射记录位掩码相应最大长度】

        数组words中可能存在由相同的字母组成的不同单词，但此时这些单词的位掩码相同。由于题目想要最大长度，即可用hashmap记录每个位掩码对应的最大单词长度。

        然后遍历哈希表中的每一对掩码，相与不为0时则更新答案。

        时间复杂度：O(L+n^2)（ L 是数组 wordswords 中的全部单词长度之和，n 是数组words 的长度）；空间复杂度：O(n)，需要创建哈希表记录每个位掩码对应的最大单词长度，哈希表中的记录数量不会超过 n。

优化后更慢了emm

执行用时：22 ms, 在所有 Java 提交中击败了41.81%的用户

内存消耗：41.4 MB, 在所有 Java 提交中击败了58.23%的用户

class Solution {
    public int maxProduct(String[] words) {
        Map<Integer, Integer> masks = new HashMap<Integer, Integer>();
        int len = words.length;
        //对每个单词进行字母掩码预处理，并找到每个位掩码对应的最大单词长度
        for(int i = 0; i < len; i++){
            int mask = 0;
            String word = words[i];
            int wordLen = word.length();
            //位掩码的第j位是1当且仅当第 j 个字母在这个单词中
            for(int j = 0; j < wordLen; j++){
                mask |= 1 << (word.charAt(j) - 'a'); //填1用或运算，减'a'表示第几个字母（1的左移量）
            }
            //该位掩码对应的最大单词长度
            if(wordLen > masks.getOrDefault(mask, 0)){
                masks.put(mask, wordLen);
            }
        }
        int ans = 0;
        //对每一对位掩码，判断无公共字母后更新最大乘积
        Set<Integer> maskSet = masks.keySet(); 
        for(int mask1 : maskSet){
            int wordLen1 = masks.get(mask1);
            for(int mask2 : maskSet){
                if((mask1 & mask2) == 0){
                    int wordLen2 = masks.get(mask2);
                    ans = Math.max(ans, wordLen1 * wordLen2);
                }
            }
        }
        return ans;
    }
}