LeetCode_位运算_中等_318.最大单词长度乘积

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] 仅包含小写字母

2.思路

（1）暴力穷举法 1

• 首先按照单词长度对 words 进行降序排序，这样可以确保我们先尝试较长的单词组合，以获得可能更大的乘积。
• 遍历所有的单词组合，对于每组单词，利用 check 方法判断它们是否有公共字母。如果没有，则计算其长度乘积，并更新 res 最终结果。
• 因为我们降序排序过，当我们找到第一个乘积较大的单词组合时，就可以直接结束循环并返回 res，避免不必要的遍历。

注意：该方法在 LeetCode 中提交时会出现“超出时间限制”的提示！

（2）暴力穷举法 2

• 首先创建一个长度为 n 的 HashSet 数组 set，每个位置上都实例化一个 HashSet 对象，用来存储对应单词的字符。
• 遍历 words 数组，将每个单词的字符逐个添加到对应的 HashSet 中。
• 循环遍历 set 数组，对于每对不同的集合 set[t] 和 set[j]（t 从 0 到 n-2，j 从 t+1 到 n-1），检查它们是否有公共字符。
• 检查方法是通过遍历 set[t]，对于集合 set[j] 中的每个字符，如果 set[t] 中也存在该字符，则将 flag 置为 1，表示有公共字符。如果 flag 仍然为 0，表示没有公共字符，则计算并更新 res 最终结果。
• 最后返回 res。

（3）位运算

• 首先创建一个长度为 words.length 的整型数组 masks，用于存储每个单词的字符掩码。
• 对于每个单词 words[i]，遍历它的每个字符，并通过位运算将对应位置上的比特位设为 1，生成字符掩码 masks[i]。这样，每个单词都可以用一个 26 位的二进制数表示，其中为 1 的位置表示单词中存在该字符。
• 创建一个变量 res 用于存储最终结果。
• 循环遍历 masks 数组的每个元素，对于每对不同的 masks[i] 和 masks[j]（i 从 0 到 n-2，j 从 i+1 到 n-1），检查它们的按位与操作是否等于 0，即两个单词没有相同字符。如果等于 0，则计算并更新 res 最终结果。
• 最后返回 res。

相较于之前的两段代码，这段代码在存储单词的字符信息时使用了位运算，将字符掩码存储在整型数组中。这样做的好处是可以通过按位与运算快速判断两个单词是否有公共字符。

3.代码实现（Java）

//思路1————暴力穷举法 1
class Solution {
    public int maxProduct(String[] words) {
        //按照单词长度对 words 进行降序排序
        Arrays.sort(words, (w1, w2) -> (w2.length() - w1.length()));
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < i + 1; j++) { 
                if (check(words[i], words[j])) {
                    int tmp = words[i].length() * words[j].length();
                    if (res < tmp) {
                        res = tmp;
                        break;
                    }
                }
            }
        }
        return res;
    }

    //判断单词 w1 和 w2 是否有公共字母
    public boolean check(String w1, String w2) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < w1.length(); i++) {
            set.add(w1.charAt(i));
        }
        for (int i = 0; i < w2.length(); i++) {
            if (set.contains(w2.charAt(i))) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

//思路2————暴力穷举法 2
class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        HashSet set[] = new HashSet[n];
        for (int i = 0; i < n; i++) {
            set[i] = new HashSet<Character>();
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                set[i].add(words[i].charAt(j));
            }
        }
        int res = 0;
        for (int t = 0; t < set.length; t++) {
            for (int j = t + 1; j < set.length; j++) {
                int flag = 0;
                for (Character c : (HashSet<Character>) set[t]) {
                    if (set[j].contains(c)) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) {
                    res = Math.max(res, words[t].length() * words[j].length());
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

//思路3————位运算
class Solution {
    public int maxProduct(String[] words) {
        int length = words.length;
        int[] masks = new int[length];
        for (int i = 0; i < length; i++) {
            String word = words[i];
            int wordLength = word.length();
            for (int j = 0; j < wordLength; j++) {
                masks[i] |= 1 << (word.charAt(j) - 'a');
            }
        }
        int res = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23