class Solution {
public:
int maxProduct(vector<string>& words) {
}
};
剑指 Offer II 005. 单词长度的最大乘积
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
示例 1:
输入: words =["abcw","baz","foo","bar","fxyz","abcdef"]输出:16 解释: 这两个单词为"abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
示例 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] 仅包含小写字母
注意：本题与主站 318 题相同：https://leetcode.cn/problems/maximum-product-of-word-lengths/
原站题解
golang 解法, 执行用时: 24 ms, 内存消耗: 6.4 MB, 提交时间: 2022-11-17 16:08:55
func maxProduct(words []string) (ans int) {
masks := map[int]int{}
for _, word := range words {
mask := 0
for _, ch := range word {
mask |= 1 << (ch - 'a')
}
if len(word) > masks[mask] {
masks[mask] = len(word)
}
}
for x, lenX := range masks {
for y, lenY := range masks {
if x&y == 0 && lenX*lenY > ans {
ans = lenX * lenY
}
}
}
return
}
python3 解法, 执行用时: 192 ms, 内存消耗: 15.3 MB, 提交时间: 2022-11-17 16:08:14
class Solution:
def maxProduct(self, words: List[str]) -> int:
masks = defaultdict(int)
for word in words:
mask = reduce(lambda a, b: a | (1 << (ord(b) - ord('a'))), word, 0)
masks[mask] = max(masks[mask], len(word))
return max((masks[x] * masks[y] for x, y in product(masks, repeat=2) if x & y == 0), default=0)