In-Depth Explanation and Solution in Python using Bit Manipulation


  • 0
    A
    class Solution(object):
        def maxProduct(self, words):
        	maxProduct = 0
        	binaryWords = []
        	for word in words:
        	    binaryWords.append(self.wordToBinary(word))
        	for i in xrange(len(words)):
        		for j in xrange(i+1,len(words)):
                            #If words do not contain like characters
        			if(not (binaryWords[i] & binaryWords[j])):
        				maxProduct = max(maxProduct, len(words[i]) * len(words[j]))
        	return maxProduct
    
        def wordToBinary(self,word):
        	num = 0
        	for char in word:
        		num |= (1 << ord(char)-ord('a'))
        	return num
    

    The only trick to this problem is finding out how to efficiently determine whether or not two words share any common letters. In order to do this, we create a new array to contain binary representation of the words. For example, the right-most bit would act as a switch to represent whether or not the word contains an 'a', the bit to the left of that a 'b', and so forth. Once our strings are represented as numbers, we can apply bitwise and (&) to any two words to find out if they share any letters in common. If the result of the & statement is 0, the two binary representations of our words do not share any common 1s. Below is an example:

    word: "ab"
    binary representation: 11 or 0011

    word: "cd"
    binary representation: 1100

    0011 & 1100 = 0, therefor these two words do not share any common letters.

    Once you've figured that out, the rest is just a matter of looping through all the words and multiplying the lengths of the ones that satisfy the above condition, while keeping track of the max.


Log in to reply
 

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