Easiest and simplest solution accepted with 40ms in C, well-explained


  • 5

    Since we are going to use the length of the word very frequently and we are to compare the letters of two words checking whether they have some letters in common:

    • using an array of int to pre-store the length of each word reducing the frequently measuring process;
    • since int has 4 bytes, a 32-bit type, and there are only 26 different letters, so we can just use one bit to indicate the existence of the letter in a word.

    • space cost O(n).
    • time cost O(n^2) -> comparing each pair of them from the beginning to the end.

    //AC - 40ms;
    int maxProduct(char** words, int wSize)
    {
        int space = sizeof(int)*wSize; //since we are going to use this value several times, store it;
        int *lens = (int*)malloc(space);
        for(int i = 0; i < wSize; i++) //pre-store the lengths for all words;
            lens[i] = strlen(words[i]);
        int *flags = (int*)malloc(space);
        memset(flags, 0, space);
        for(int i = 0; i < wSize; i++) //retrieve the bit-flag from word;
            for(int j = 0; words[i][j]; j++)
                flags[i] |= 1<<(words[i][j]-'a');
        int max = 0;
        for(int i = 0; i < wSize; i++) //traversing each pair of two different words;
            for(int j = i+1; j < wSize; j++)
                if(!(flags[i] & flags[j]))
                {
                    int t = lens[i]*lens[j];
                    if(t > max)
                        max = t;
                }
        return max;
    }

  • 0

    C++ solution enclosed too.

    int maxProduct(vector<string>& words) {
        vector<int> mask(words.size());
        vector<int> lens(words.size());
        for(int i = 0; i < words.size(); ++i) lens[i] = words[i].length();
        int result = 0;
        for (int i=0; i<words.size(); ++i) {
            for (char c : words[i])
                mask[i] |= 1 << (c - 'a');
            for (int j=0; j<i; ++j)
                if (!(mask[i] & mask[j]))
                    result = max(result, lens[i]*lens[j]);
        }
        return result;
    }
    

Log in to reply
 

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