LeetCode 最大单词长度乘积题解

LeetCode 最大单词长度乘积题解

题目描述

给定一个字符串数组 words，找出其中两个不包含相同字符的单词之间的最大乘积。如果不存在这样的两个单词，则返回 0。

示例：

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

解题思路

方法：位运算

思路：

• 使用位运算来解决这个问题。
• 对于每个单词，计算其字符对应的位掩码。
• 如果两个单词没有相同字符，则它们的位掩码进行与运算结果为 0。
• 遍历所有单词对，找出最大乘积。

复杂度分析：

• 时间复杂度：O(n^2)，其中 n 是单词的数量。
• 空间复杂度：O(n)。

代码实现

方法：位运算

# 最大单词长度乘积（位运算） def max_product(words): n = len(words) masks = [] lengths = [] for word in words: mask = 0 for char in set(word): mask |= 1 << (ord(char) - ord('a')) masks.append(mask) lengths.append(len(word)) max_product_val = 0 for i in range(n): for j in range(i + 1, n): if masks[i] & masks[j] == 0: max_product_val = max(max_product_val, lengths[i] * lengths[j]) return max_product_val # 测试 def test_max_product(): words = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] print(max_product(words)) # 输出：16 if __name__ == "__main__": test_max_product()

测试用例

测试用例 1：基本情况

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

总结

最大单词长度乘积是一个经典的位运算问题，它可以通过位运算来高效地解决。

位运算的核心思想是：使用位掩码表示每个单词包含的字符，如果两个单词没有相同字符，则它们的位掩码进行与运算结果为 0。

掌握位运算的使用方法，对于解决类似的问题非常重要。