JavaScript: Simple commented bit map solution


  • 0
    O

    Here is my simple solution for using a bit map for quick word matching. The code is commented so as to make it clear what is going on. Basically the flow here is to create a bitMap where every true bit in the number matches to a character in the word. Eg, 'a' matches to the first bit and 'c' matches to the 3rd. Then we can just compare the bit maps from two words and if they share a common true bit, they have the same character.

    /*
     * Here we are turning a word into a number where each 1 bit in the number
     * corresponds to the word having that character. Each character is at a bit
     * offset relative to where it is from the letter 'a'. Eg, 'c' is the 3rd bit.
     */
    var getByteMap = function (word) {
        var byteMap = 0,
            aCode = 'a'.charCodeAt(0), // Using 'a' as the base
            currCode,
            index;
            
        for (index = 0; index < word.length; index++) {
            currCode = word.charCodeAt(index);
            
            // We're OR'ing onto the byteMap value because we only care
            // about unique letters, so two of the same letter won't
            // affect the value.
            byteMap |= 1 << (currCode - aCode);
        }
        
        return byteMap;
    };
    
    /**
     * @param {string[]} words
     * @return {number}
     */
    var maxProduct = function(words) {
        var wordByteMap = {},
            maxProduct = 0,
            currProduct, i, j;
            
        // Generate the byte map first for quick word matching.
        for (i = 0; i < words.length; i++) {
            wordByteMap[words[i]] = getByteMap(words[i]);
        }
            
        for (i = 0; i < words.length - 1; i++) {
            for (j = i+1; j < words.length; j++) {
                // This compares the bits set between the two words byteMaps.
                // If any bits match (meaning the words share a character)
                // then this will be false.
                if (!(wordByteMap[words[i]] & wordByteMap[words[j]])) {
                    currProduct = words[i].length * words[j].length;
                    if (currProduct > maxProduct) {
                        maxProduct = currProduct;
                    }
                }
            }
        }
        
        return maxProduct;
    };

Log in to reply
 

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