318. 最大单词长度乘积

🟠   🔖  位运算 数组 字符串  🔗 力扣 LeetCode

题目

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.

题目大意

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

示例 1：

输入： words = ["abcw","baz","foo","bar","xtfn","abcdef"]

**输出：**16

解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入： words = ["a","ab","abc","d","cd","bcd","abcd"]

**输出：**4

解释： 这两个单词为 "ab", "cd"。

示例 3：

输入： words = ["a","aa","aaa","aaaa"]

**输出：**0

解释：不存在这样的两个单词。

提示：

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

解题思路

1. 构造位掩码：

   • 对每个单词，遍历其字符，根据字符的 ASCII 值计算相应位的位置，将该位置的二进制位设为 1。

2. 比较两两单词：

   • 用两层循环比较所有单词对。
   • 如果两个单词的位掩码按位与的结果为 0，则计算它们长度的乘积，并更新最大值。

3. 返回结果：

   • 最后返回最大乘积。

复杂度分析

• 时间复杂度：O(n * L + n^2)

  • 构造位掩码：对每个单词遍历其字符，复杂度为 O(n * L)，其中 n 是单词数，L 是单词的平均长度。
  • 比较两两单词：两层循环，复杂度为 O(n^2)。
  • 整体复杂度为 O(n * L + n^2)。

• 空间复杂度：O(n)，存储每个单词的位掩码。

代码

/**
 * @param {string[]} words
 * @return {number}
 */
var maxProduct = function (words) {
	// 构造每个单词的位掩码
	const values = words.map((word) => {
		let mask = 0;
		for (let char of word) {
			mask |= 1 << (char.charCodeAt() - 97); // 将对应字母位置的二进制位设为 1
		}
		return mask;
	});

	let maxProduct = 0;

	// 比较两两单词
	for (let i = 0; i < words.length; i++) {
		for (let j = i + 1; j < words.length; j++) {
			// 如果没有公共字母，计算长度乘积
			if ((values[i] & values[j]) === 0) {
				maxProduct = Math.max(maxProduct, words[i].length * words[j].length);
			}
		}
	}

	return maxProduct;
};