题目大意：
最大单词长度乘积
给定一个字符串数组 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 解释: 不存在这样的两个单词。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=318
解题思路分析：
这道题要找到最长的两个不含公共字母的单词，我们没有别的办法，必须使用两层循环对单词进行两两的比较。而本题优化的关键在于比较的方式。如果无脑使用contains方法去逐个检查某一个单词上的每个字母是否出现在另一个单词中的话，这样做的效率毫无疑问会非常低下。因此本题我们需要对每一个单词进行预处理，事先查看每个单词都包含了哪些字母。我们可以使用一个二维数组来记录每个单词包含字母的状态。
int[][] count = new int[words.length][26];
其中count[i][j]代表，第i个单词中包含字母j的个数，字母j的下标是0-25，分别代表字母a-z。
这样，在2个单词进行比较时，我们从0循环至25，查看两个单词对应的每个字母是否有同时出现的情况，如果有，说明两个单词不能配对。反之则代表可以，我们将两个单词的长度相乘，用得到的结果去更新全局最大值即可。
这一种解法可以通过所有的TC，执行时间在23ms左右（faster than 43.34%），我们在文章后面会给出实现代码。其实本题还有更加高效的方式，其原理与上面的解法大同小异，只不过我们使用了一个int整数替代数组，来表示一个单词中每种字母出现与否。我们用0代表该字母没有出现过，1代表出现过，因此一个单词中所有字母出现的情况我们可以使用一组01的二进制数字来表示，比如abz，我们可以表示为11000….0001（中间省略的都是0）。然后对于任意两个单词，我们只要将他们的状态进行并运算（位运算），如果结果是0，代表他们没有相同字母，即可以进行乘积。
实现代码：
public int maxProduct(String[] words) {
int[] bitmap = new int[words.length];
for(int i=0;i<words.length;i++){
char[] arr=words[i].toCharArray();
int bit=0;
for(int j=0;j<arr.length;j++){
bit |= (1<<(arr[j]-'a'));
}
bitmap[i]=bit;
}
int max=0;
for(int i=0;i<words.length;i++){
for(int j=i+1;j<words.length;j++){
if((bitmap[i]&bitmap[j])==0){
max=Math.max(max,words[i].length()*words[j].length());
}
}
}
return max;
} 本题解法执行时间为6ms。
Runtime: 6 ms, faster than 99.77% of Java online submissions for Maximum Product of Word Lengths.
Memory Usage: 39.4 MB, less than 36.84% of Java online submissions for Maximum Product of Word Lengths.
数组版本代码：
public int maxProduct(String[] words) {
int[][] count = new int[words.length][26];
for(int i=0;i<words.length;i++){
char[] arr=words[i].toCharArray();
for(int j=0;j<arr.length;j++){
count[i][arr[j]-'a']++;
}
}
int max=0;
for(int i=0;i<words.length;i++){
for(int j=i+1;j<words.length;j++){
boolean isValid=true;
for(int k=0;k<26;k++){
if(count[i][k]>0&&count[j][k]>0){
isValid=false;
break;
}
}
if(isValid) max=Math.max(max,words[i].length()*words[j].length());
}
}
return max;
} Runtime: 24 ms, faster than 42.32% of Java online submissions for Maximum Product of Word Lengths.
Memory Usage: 39.4 MB, less than 36.84% of Java online submissions for Maximum Product of Word Lengths.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-318-maximum-product-of-word-lengths-解题思路分析/