def maxProduct(self, words): n, res = len(words), 0 word_bits = [0 for i in range(n)] # generate a 26 bit mask for every word, each set to 1 if a character is set for i in range(n): for c in words[i]: mask = 1 << (ord(c) - 96) word_bits[i] = word_bits[i] | mask # for each word, compre to every other word for i in range(n): for j in range(i+1, n): # if the AND of the two bits are zero, then no overlapping characters if word_bits[i] & word_bits[j] == 0: res = max(res, len(words[i]) * len(words[j])) return res
Keep is to use a bit vector to keep track of which characters are set for each word. For example, if we have word
ade, then we can represent this with
10011, where a is the first bit, and e is the last bit etc. There are two zero bits to represent the missing
Now to check if two words have the same characters, we just need to do an & of their vectors. If the result is 0, then there is no overlapping characters.