|
给你一个字符串数组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]仅包含小写字母
这题让返回的是两个字符串长度乘积的最大值，并且这两个字符串还不能有公共的字母。如果计算两个字符串长度的乘积，这个比较简单，我们只需要两两计算即可，关键是我们怎么确定相乘的两个字符串没有公共的字母，当然这个判断的方式也比较多，我们这里来使用位运算来判断。
题中说了words[i]仅包含小写字母，小写字母的个数是26，我们可以使用一个int类型来表示，因为int类型是32位足够了，比如字符串"abcw"表示方式
判断两个字符串是否有公共的字母，只需要判断判断他们的(&运算)是否为0即可，如果结果是0，表示他们没有公共的字母，我们来看下代码
public int maxProduct(String[] words) {
//记录每个字符串中有哪些字母
int[] bits = new int[words.length];
int res = 0;
for (int i = 0; i < words.length; ++i) {
//标记当前字符串有哪些字母
for (char ch : words[i].toCharArray())
bits[i] |= 1 << (ch - 'a');
//如果当前字符串和之前的字符串没有公共的字母，就计算他们的
//乘积，保留最大值即可
for (int j = 0; j < i; ++j) {
//如果结果为0，表示他们没有公共的字母
if ((bits[i] & bits[j]) == 0)
res = Math.max(res, (words[i].length() * words[j].length()));
}
}
return res;
}
|
