「每日LeetCode」2021年8月21日

本文最后更新于：2023年3月19日 晚上

剑指 Offer II 005. 单词长度的最大乘积

剑指 Offer II 005. 单词长度的最大乘积

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
示例  1:

1
2
3
输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。

示例 2:

1
2
3
输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。

示例 3:

1
2
3
输入: words = ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。

提示：

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

注意：本题与主站 318  题相同：https://leetcode-cn.com/problems/maximum-product-of-word-lengths/

思路

map 返回一个对象，计算每个字符的 set 及原字符串。按照 set 的 size 从大到小排列。遍历所有字符，比较两个集合是否有交集，没有的话更新并计算最大的字符长度乘积，最后返回即可。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {string[]} words
 * @return {number}
 */
var maxProduct = function (words) {
  let max = 0;
  words = words
    .map((word) => {
      return { set: new Set(word.split("")), word };
    })
    .sort((a, b) => b.set.size - a.set.size);

  const check = (set1, set2) => {
    const [maxSet, minSet] = [set1, set2].sort(
      (a, b) => b.set.size - a.set.size
    );
    return [...minSet.set].every((char) => !maxSet.set.has(char));
  };
  for (let i = 0; i < words.length; i++) {
    const set1 = words[i];
    for (let j = i + 1; j < words.length; j++) {
      const set2 = words[j];
      if (check(set1, set2))
        max = Math.max(max, set1.word.length * set2.word.length);
    }
  }
  return max;
};