*大单词长度乘积(JS实现)

1 题目
给定一个字符串数组 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-cn.com/problems/maximum-product-of-word-lengths

2 思路
这道题的关键点在于如何快速判断两个单词是否有公共字符,因此就想到了利用位运算,我们可以将一个单词转换为数字,a代表1,b代表2,c代表4依次类推,注意相同的字符只加一次,判断两个单词是否有公共字符时只需将两个数字作&运算看结果是否为0即可,当然可能有多个单词转换后的数字相同,但我们只需要*长单词的长度即可

3代码
/**
* @param {string[]} words
* @return {number}
*/
var maxProduct = function(words) {
let map = {};

for (let word of words) {
let bit = count(word);
if (map[bit]) { //只保留*大长度
map[bit] = Math.max(map[bit], word.length);
} else {
map[bit] = word.length;
}
}

let wordBits = Object.keys(map);

let max = 0;
for (let i=0; i<wordBits.length; i++) {
for (let j=i+1; j<wordBits.length; j++) {
if ((parseInt(wordBits[i]) & parseInt(wordBits[j])) === 0) {
max = Math.max(max, map[wordBits[i]] * map[wordBits[j]]);
}
}
}

return max;

function count(word) { //计算单词的对应的数字
let sum = 0;
let startIndex = ‘a’.charCodeAt(0);
let map1 = {};

for (let alpha of word) {
if (map1[alpha]) continue;
map1[alpha] = true;
sum += 1 << (alpha.charCodeAt() – startIndex);
}

return sum;
}
};