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。掌握位运算的使用方法对于解决类似的问题非常重要。