My C++ solution, 90 ms, O(N^2) complexity, O(N) space and some thoughts


  • 2
    D

    The basic idea is to use a bit mask bitMask[i] (a special case on unordered_set) to represent the letters in the word words[i] and then compare each possible word pair (words[i] and word[j], i != j) to see if they have any common letters (bitMask[i] & bitMask[j] !=0). If not, update res;
    One trick that might help speed in some cases is to sort words in a descending order of the word size and then do early stop.
    Generally speaking, it is O(N^2) time complexity.

    class Solution {
    public:
        int maxProduct(vector<string>& words) {
            int wSize = words.size(), res=0, i, j;
            if(wSize<=1) return res;
            unsigned int bitMask[wSize] ={0};
            // sort words in a descending order of word length 
            sort(words.begin(),words.end(), [](string &left, string &right) {return left.size()>right.size();});
            //build letter bit mask for each word;
            for(i=0; i<wSize; ++i)
                for(j=0; j<words[i].size(); ++j) bitMask[i] |= 1<<(words[i][j]-'a');
            // compare each word pair with early stop (if the remaining word pairs can not generate a larger res, then return)   
            for(i=0; i<wSize-1 && res < int(words[i].size())*int(words[i+1].size()) ;++i)
                for(j=i+1; j<wSize; ++j) 
                    if(!(bitMask[i] & bitMask[j])) 
                    {
                        res = max(res, int(words[i].size()) * int(words[j].size()));
                        break;
                    }
            return res;        
                    
        }
    };
    

    Another thought, since we sort the words array, we may be able to take advantage of that, Say use another Bit Vector letterMask[j] kind of data structure to save all the word indices i that words[i] don't have letter 'a'+j. Then use bit and operation to find all the words that don't have all the letters in words[i]. Then use some bit operation trick (e.g. find the rightmost "1" bit) to find the one with the longest size. Following this line, I came up with the following solution, but it performs even worse, 100ms.
    Not sure how to come up a better solution,

    class Solution {
    public:
        int maxProduct(vector<string>& words) {
            int wSize = words.size(), res=0, i, j, k, bigI;
            if(wSize<=1) return res;
            int bitMask[wSize] = {0};
            const int lSize = 1 + (wSize-1)/32;
            //vector<vector<int>> letMask(26, vector<int>(lSize, 0));
            int letMask[26][lSize] ;
            fill_n(&letMask[0][0], 26*lSize, 0);
    		unsigned int temp;
            
            unordered_map<unsigned int, int> map;
            for(i=0; i<32; ++i) map[1<<i] = i;
            sort(words.begin(),words.end(), [](string &left, string &right) {return left.size()>right.size();});
           
            for(i=0; i<wSize; ++i)
                for(j=0; j<words[i].size(); ++j) 
                {
                    bitMask[i] |= 1<<(words[i][j]-'a');
                    letMask[words[i][j]-'a'][i>>5] |= 1<<(i % 32 );
                }
                
            for(i=0; i<wSize-1 && res < int(words[i].size())*int(words[i+1].size()) ;++i)
            {
                for(k=0; k<lSize; ++k)
                {
                    for(j=0, temp = 0; j<26; ++j)
                        if(bitMask[i] & (1<<j))
    					{
    						temp |= letMask[j][k];
    					}
                    temp = ~temp;
                    if(temp!=0)
                    {
                        bigI = k*32 + map[temp & -temp];
    					if(bigI<wSize)
    					{
    						res = max(res, int(words[i].size()) * int(words[bigI].size()));
    						break;
    					}
                    }
                }
            }
            return res;        
                    
        }
    };

Log in to reply
 

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