Lt318. 最大单词长度乘积

318. 最大单词长度乘积

给定一个字符串数组 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 **解释: **不存在这样的两个单词。
​

提示：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 仅包含小写字母

思路

遍历每个字符将对应的位数设为 1，转化为 2 进制数。再 ON2 遍历每个单词，与计算判断是否有重复的字母，没有的话乘计算最大值。

解答

/**
 * @param {string[]} words
 * @return {number}
 */
const maxProduct = function (words) {
  const hash = words.map((word) => {
    const arr = new Array(26).fill(0);
    for (const char of word) {
      arr[char.charCodeAt() - 97] = 1;
    }
    return parseInt(arr.join(""), 2);
  });

  let max = 0;
  for (let i = 0; i < words.length; i++) {
    const word1 = words[i];
    for (let j = i + 1; j < words.length; j++) {
      const word2 = words[j];
      if (!(hash[i] & hash[j]))
        max = Math.max(word1.length * word2.length, max);
    }
  }
  return max;
};