https://leetcode.com/problems/maximum-product-of-word-lengths/
Given 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 <= 1000
1 <= words[i].length <= 1000
words[i] consists only of lowercase English letters.
- code
class Solution:
def maxProduct(self, words: List[str]) -> int:
res = 0
n = len(words)
for i in range(n):
for j in range(i + 1, n):
if len(set(words[i]) & set(words[j])) == 0:
res = max(res, len(words[i]) * len(words[j]))
return res
- code
class Solution:
def maxProduct(self, words: List[str]) -> int:
m = defaultdict(int)
bit_num = lambda x: ord(x) - ord('a')
for w in words:
bitmask = 0
for c in w:
bitmask |= 1 << bit_num(c)
m[bitmask] = max(m[bitmask], len(w))
res = 0
for x in m:
for y in m:
if x & y == 0:
res = max(res, m[x] * m[y])
return res