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

  • 1
    class Solution {
    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++){
                    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.