Detailed explanation about how int array works in this problem


  • 0
    X

    Solution:

    detect/save what letters a word has.

    calculate product and save the result if it's greater than former result.

    /**
     * Find max product of two strings that don't share same letters in array
     *
     * @param words an Array that save a serious of Strings
     * @return max product of two words in array.
     */
    public int maxProductBitMap(String[] words) {
        if (null == words || words.length < 2)
            return 0;
        // initialize a int array to store what letters a word has.
        int[] lettersOfWord = new int[words.length];
    
        // traverse each word
        for (int wordIndex = 0; wordIndex < words.length; wordIndex++) {
            // traverse each letter of word, than save what it has into lettersOfWord
            // if two letters are found, say 'a' and 'c', make last bit to 0000 **** 0101.
            for (int letterIndex = 0; letterIndex < words[wordIndex].length(); letterIndex++)
                lettersOfWord[wordIndex] |= 1 << words[wordIndex].charAt(letterIndex) - 'a';
        }
    
        int maxProductValue = 0;
        // outer loop
        for (int wordOuterIndex = 1; wordOuterIndex < words.length; wordOuterIndex++) {
            // inner loop
            for (int wordInnerIndex = 0; wordInnerIndex < wordOuterIndex; wordInnerIndex++) {
                // two words should have no letters in common
                // product of current two words should greater than prior max product value
                if (0 == (lettersOfWord[wordInnerIndex] & lettersOfWord[wordOuterIndex])
                        && words[wordInnerIndex].length() * words[wordOuterIndex].length() > maxProductValue)
                    maxProductValue = words[wordInnerIndex].length() * words[wordOuterIndex].length();
            }
        }
        return maxProductValue;
    }
    

    More Explanation:
    The reason use 1<< is that let the value of 'a' to be 1, otherwise, 'a' will be missed since 'a' - 'a' = 0.

    It is possible that two words (different length) may has same value in lettersOfWord.

    Example, "abcd" and "aabbccdd" will both return 0000 ***0 1111

    But we don't care how many times of a character occurs in one word, we just want to record what letters occurs in one word, so that we can use AND operation to compare if two words has the same letter afterwards.

    for prior case, 0000 ***0 1111 & 0000 ***0 1111 equals to **** 1111 which means has same letter.

    another case would be "abcd" and "efgh",

    0000 **** 0000 1111 & 0000 **** 1111 0000 equals to 0000 **** 0000, which means these two words don't have same letters.

    Reference: Chinese Version(partial English)


Log in to reply
 

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