LeetCode 솔루션 분류
318. Maximum Product of Word Lengths
본문
Medium
201699Add to ListShareGiven a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
Example 1:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".
Example 2:
Input: words = ["a","ab","abc","d","cd","bcd","abcd"] Output: 4 Explanation: The two words can be "ab", "cd".
Example 3:
Input: words = ["a","aa","aaa","aaaa"] Output: 0 Explanation: No such pair of words.
Constraints:
2 <= words.length <= 10001 <= words[i].length <= 1000words[i]consists only of lowercase English letters.
관련자료
-
링크
댓글 1
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 81 ms, faster than 48.84% of C++ online submissions for Maximum Product of Word Lengths.
Memory Usage: 15.6 MB, less than 79.69% of C++ online submissions for Maximum Product of Word Lengths.
Runtime: 81 ms, faster than 48.84% of C++ online submissions for Maximum Product of Word Lengths.
Memory Usage: 15.6 MB, less than 79.69% of C++ online submissions for Maximum Product of Word Lengths.
class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
vector<int> masks(n, 0);
for (int i = 0; i < n; ++i) {
for (auto c : words[i]) {
masks[i] |= 1 << (c - 'a');
}
}
int res = 0;
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if ((masks[i] & masks[j]) == 0) {
int tmp = words[i].size() * words[j].size();
res = max(res, tmp);
}
}
}
return res;
}
};
