难度: Medium
给你一个字符串数组 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 <= 10001 <= words[i].length <= 1000words[i] 仅包含小写字母运行时间: 174 ms
内存: 19.0 MB
class Solution:
def maxProduct(self, words: List[str]) -> int:
# mask = [0] * len(words)
# res = 0
# n = len(words)
# for i in range(n):
# for c in words[i]:
# mask[i] |= 1 << (ord(c)-ord('a'))
# for j in range(i):
# if len(words[j]) > res / len(words[i]):
# if mask[i] & mask[j] == 0:
# res = max(res, len(words[i]*len(words[j])))
# return res
word_max_length = {} # 存储每个字符串字符掩码和对应的最大长度
# 统计每个字符出现过的字母，生成其字符掩码，并记录对应的最大字符串长度
for word in words:
mask = 0
word_length = len(word)
for c in word:
mask |= 1 << (ord(c) - ord('a')) # 将出现的字符对应的位置1
word_max_length[mask] = max(word_max_length.get(mask, 0), word_length) # 更新这个字符掩码的最大长度
res = 0
# 双重循环枚举哈希表中的所有字符掩码对
for key1, len1 in word_max_length.items():
for key2, len2 in word_max_length.items():
# 如果两个字符掩码位与为0，说明二进制每个位置的值都不同，即两个字符串出现的字符不一样
if (key1 & key2) == 0:
res = max(res, len1 * len2)
return res
这个题解采用了位运算和哈希表的思路。首先用一个哈希表记录每个单词出现过的字符所对应的二进制掩码，以及该掩码对应的最大单词长度。然后通过双重循环枚举哈希表中的所有掩码对，如果两个掩码按位与的结果为0，说明它们对应的单词没有公共字母，此时更新最大乘积结果。
时间复杂度: O(nm)
空间复杂度: O(1)
class Solution:
def maxProduct(self, words: List[str]) -> int:
word_max_length = {} # 存储每个字符串字符掩码和对应的最大长度
# 统计每个字符出现过的字母，生成其字符掩码，并记录对应的最大字符串长度
for word in words:
mask = 0
word_length = len(word)
for c in word:
mask |= 1 << (ord(c) - ord('a')) # 将出现的字符对应的位置1
word_max_length[mask] = max(word_max_length.get(mask, 0), word_length) # 更新这个字符掩码的最大长度
res = 0
# 双重循环枚举哈希表中的所有字符掩码对
for key1, len1 in word_max_length.items():
for key2, len2 in word_max_length.items():
# 如果两个字符掩码位与为0，说明二进制每个位置的值都不同，即两个字符串出现的字符不一样
if (key1 & key2) == 0:
res = max(res, len1 * len2)
return res
在构建字符掩码时，每个字母的存在性是由对应位（position）的二进制位值来表示的，即通过 '1 << (ord(c) - ord('a'))' 操作将字母对应的位设为1。由于这是位或操作 '|='，即使单词中的字母重复出现，其对应的位只会从0变为1一次，后续相同字母的再次出现不会改变已经设为1的位值，因此每个字母只会被计算一次。
在计算两个单词长度的乘积以求得最大值时，只有最长的单词会贡献最大乘积，因此只需要记录每个独特字符掩码的最大单词长度。保存所有长度会增加空间复杂性而没有实际计算价值，因为只有最长的单词长度才是我们需要的，以此来优化空间和计算效率。
英文字母表中有26个字母，每个字母可以表示为一个二进制位，所有可能的字母组合可以通过26个二进制位表示。因此，所有可能的字符掩码数是2^26（每个位可以是0或1），对应于所有可能的从空集到全集的字母组合。这是为什么哈希表大小最多是2^26的原因，因为这是26个字母所有可能组合的数量。
按位与操作（&）用于确定两个字符掩码是否有公共位被设为1，即两个单词是否有共同的字母。如果两个掩码在某一位上都是1，那么这个位的按位与结果也是1，表示两个单词共享至少一个字母。如果按位与的结果为0，表示两个掩码没有任何公共的1位，即对应的两个单词没有公共字母。这种方法是高效的，因为它通过一次简单的位操作即可判断两个单词是否存在公共字母。