Python Solution --- Easy to understand!

  • 0
    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 b, c.

    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.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.