318 Maximum Product of Word Lengths
Given a string array
words, find the maximum value oflength(word[i]) * length(word[j])where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.Example 1:
Given
["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return16
The two words can be"abcw", "xtfn".Example 2:
Given
["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return4
The two words can be"ab", "cd".Example 3:
Given
["a", "aa", "aaa", "aaaa"]
Return0
No such pair of words.The Idea: For each combination of words whose intersection return the empty set, return the maximum product of their lengths.
Complexity: O(n^2 * m) where N is the number of words, and M is the length of a word.
class Solution:
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
max_prod = 0
for i in range(0, len(words)):
for j in range(i + 1, len(words)):
if set(words[i]) & set(words[j]) == set():
max_prod = max(len(words[i]) * len(words[j]), max_prod)
return max_prod
The Idea: Create a unique binary representation of the each word. We can do so by setting each bit for each character in the word. Then we can do the same thing as before and check if the intersection of each word (in this case there binary fingerprint), and look for the empty set, or 0.
Complexity: O(2N*M) time and O(N) space
import string
class Solution:
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
char_int = {char: i for i, char in enumerate(list(string.ascii_lowercase))}
word_map = [0] * len(words)
for i, word in enumerate(words):
for char in word:
word_map[i] |= 1 << char_int[char]
max_product = 0
for i in range(0, len(words)):
for j in range(i+1, len(words)):
if not word_map[i] & word_map[j]: # O(1) processing time
max_product = max(max_product, len(words[i]) * len(words[j]))
return max_product
Last modified 4yr ago