题目描述

给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个单词,返回 0 。

示例

输入:words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出:16
解释:这两个单词为 "abcw", "xtfn"

Coding

class Solution {
public int maxProduct(String[] words) {
int ans = 0;
int n = words.length;
int[] nums = new int[n];
int idx = 0;
for(String str:words){
nums[idx++] = convert(str);
}
//用每个单词一次去和其他单词做&运算,结果为0说明不含有公共单词,&运算:对应位都为1才为1,否则为0
for(int i = 0;i < n;i++){
for(int j = i + 1;j < n;j++){
if((nums[i] & nums[j]) == 0){
ans = Math.max(ans,words[i].length() * words[j].length());
}
}
}
return ans;
}
//将每个单词映射到一个int类型变量上
//abcd 对应二进制位从低到高 |运算:对应为都为0才为0,否则为1
public int convert(String s){
int ans = 0;
for(int i = 0;i < s.length();i++){
ans |= (1 << (s.charAt(i) - 'a'));
}
return ans;
}
}