class Solution {
public:
int maxProduct(vector<string>& words) {
}
};
318. 最大单词长度乘积
给你一个字符串数组 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] 仅包含小写字母原站题解
cpp 解法, 执行用时: 52 ms, 内存消耗: 24.2 MB, 提交时间: 2023-11-06 00:08:41
class Solution {
public:
int maxProduct(vector<string>& words) {
int length = words.size();
vector<int> masks(length);
for (int i = 0; i < length; i++) {
string word = words[i];
int wordLength = word.size();
for (int j = 0; j < wordLength; j++) {
masks[i] |= 1 << (word[j] - 'a');
}
}
int maxProd = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if ((masks[i] & masks[j]) == 0) {
maxProd = max(maxProd, int(words[i].size() * words[j].size()));
}
}
}
return maxProd;
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 42.7 MB, 提交时间: 2023-11-06 00:08:17
class Solution {
public int maxProduct(String[] words) {
int length = words.length;
int[] masks = new int[length];
for (int i = 0; i < length; i++) {
String word = words[i];
int wordLength = word.length();
for (int j = 0; j < wordLength; j++) {
masks[i] |= 1 << (word.charAt(j) - 'a');
}
}
int maxProd = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if ((masks[i] & masks[j]) == 0) {
maxProd = Math.max(maxProd, words[i].length() * words[j].length());
}
}
}
return maxProd;
}
}
python3 解法, 执行用时: 356 ms, 内存消耗: 17.2 MB, 提交时间: 2022-11-16 11:18:27
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)
golang 解法, 执行用时: 28 ms, 内存消耗: 8.5 MB, 提交时间: 2022-11-16 11:17:53
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
}
golang 解法, 执行用时: 28 ms, 内存消耗: 8.4 MB, 提交时间: 2022-11-16 11:17:10
func maxProduct(words []string) (ans int) {
masks := make([]int, len(words))
for i, word := range words {
for _, ch := range word {
masks[i] |= 1 << (ch - 'a')
}
}
for i, x := range masks {
for j, y := range masks[:i] {
if x&y == 0 && len(words[i])*len(words[j]) > ans {
ans = len(words[i]) * len(words[j])
}
}
}
return
}
python3 解法, 执行用时: 784 ms, 内存消耗: 17.4 MB, 提交时间: 2022-11-16 11:16:38
class Solution:
def maxProduct(self, words: List[str]) -> int:
masks = [reduce(lambda a, b: a | (1 << (ord(b) - ord('a'))), word, 0) for word in words]
return max((len(x[1]) * len(y[1]) for x, y in product(zip(masks, words), repeat=2) if x[0] & y[0] == 0), default=0)