• 欢迎光临~

318. Maximum Product of Word Lengths

Given a string array `words`, return the maximum value of `length(word[i]) * length(word[j])` where the two words do not share common letters. If no such two words exist, return `0`.

Example 1:

```Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
```

Example 2:

```Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
```

Example 3:

```Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words. ```

Constraints:

• `2 <= words.length <= 1000`
• `1 <= words[i].length <= 1000`
• `words[i]` consists only of lowercase English letters.

```class Solution {
public int maxProduct(String[] words) {
int max = 0;
for(int i=0;i<words.length-1;i++){
for(int j=i+1;j<words.length;j++){
if(!hasCommon(words[i],words[j]))
max = Math.max(max,words[i].length()*words[j].length());
}
}
return max;
}
private boolean hasCommon(String w1,String w2){
for(char c : w1.toCharArray()){
if(w2.indexOf(c)>=0) return true;
}
return false;
}
}```

```class Solution {
public int maxProduct(String[] words) {
int max = 0;
int[] state = new int[words.length];
for(int i=0;i<words.length;i++){
state[i] = getState(words[i]);
}
for(int i=0;i<words.length-1;i++){
for(int j=i+1;j<words.length;j++){
if( (state[i] & state[j]) ==0 )
max = Math.max(max,words[i].length()*words[j].length());
}
}
return max;
}
private int getState(String str){
for(char c:str.toCharArray()){
int pos = c-'a';
}
}
}```

```class Solution {
public int maxProduct(String[] words) {
int max = 0;
Map<Integer,Integer> map = new HashMap();

for(int i=0;i<words.length;i++){
int bitValue = getState(words[i]);
map.put(bitValue, Math.max(map.getOrDefault(bitValue,0), words[i].length()));
}
int result = 0;
for(int i:map.keySet()){
for(int j:map.keySet()){
if( i!=j && ( (i & j) == 0))
result = Math.max(result, map.get(i)*map.get(j));
}
}
return result;
}
private int getState(String str){