题目描述:给定一个字符串数组 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
解释: 不存在这样的两个单词。
提示:2 <= words.length <= 10001 <= words[i].length <= 1000
题目分析:这道题首先要做的就是判断两个字符串中是否含有重复的字母，解决了这个问题也就解决了这道题的关键点。你可能想到用暴力求解，但这道题运用位运算的方法就能解决这个关键问题。我们可以为每个字符串建立一个长度为 26 的二进制数字，每个位置表示是否存在该字母。如果两个字母串含有重复数字，那它们的二进制表示的按位与不为 0。我们可以先用循环遍历这个数组，然后获取对应单词的位掩码。最后再进行一次循环，通过计算它们的位掩码按位与是否结果为 0 判断是否包含重复字母，如果没有重复的字母，则计算它们的长度之积，并与最大单词长度乘积进行比较，保留其中最大的值。最后返回最大单词长度乘积值即可。当然下面的解法是使用数组的形式，但你也可以使用 map 对其进行优化。 题解:执行用时: 7 ms 内存消耗: 38.3 MB class Solution {
public int maxProduct(String[] words) {
// 单词个数
int n = words.length;
// 单词位掩码数组
int[] masks = new int[n];
// 单词长度数组
int[] lens = new int[n];
// 临时位掩码
int bitmask = 0;
// 循环遍历每个单词
for (int i = 0; i < n; ++i) {
bitmask = 0;
// 获取单词对应的位掩码
for (char ch : words[i].toCharArray()) {
// (int)ch - (int)'a' 是计算该字母在掩码中的位置
// 1 << x 创建一个第 x 位为 1 的掩码
// bitmask |= x 通过或操作将该码合并到位掩码中
bitmask |= 1 << ((int)ch - (int)'a');
}
// 保存单词的位掩码
masks[i] = bitmask;
// 保存单词的长度
lens[i] = words[i].length();
}
// 最大单词长度乘积
int maxVal = 0;
// 循环
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
// 判断两个单词是否包含公共字母
if ((masks[i] & masks[j]) == 0) {
// 如果没有则计算它们长度的乘积并与原来的最大乘积比较
maxVal = Math.max(maxVal, lens[i] * lens[j]);
}
}
}
// 返回最大长度乘积
return maxVal;
}
}
|
