C++ bit Manipulation solution with explanation, 120ms beat 83%


  • 1
    H
    class Solution {
    public:
    int maxProduct(vector<string>& words) {
        int*p = new int[words.size()];
        for(int i = 0; i<words.size(); i++){
            p[i] = 0;
            for(int j = 0; j<words[i].size(); j++){
                p[i] = p[i]|(1<<(words[i][j]-'a'));
            }
        }
        int res = 0;
        for(int i = 0; i<words.size(); i++){
            for(int j = i+1; j<words.size(); j++){
                if((p[i]&p[j])==0){
                    int tmp = words[i].size()*words[j].size();
                    res = max(res, tmp);
                }
            }
        }
        return res;
    }
    };
    
    • for each word, I use a array to convert the word to a int. For example, the word: "abef" will be converted to 110011, which means each letter occupy one position such as letter 'a' occupy first position, letter 'c' occupy the third position, and so on.
    • than, I use O(n*n) solution, which just & two int, and check if it is equal to zero.

Log in to reply
 

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