leetcode 318

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int length = words.size();
        vector<int>masks(length);

        for(int i=0; i<length; i++){
            string word = words[i];

            int wordl = word.size();
            for(int j=0; j<wordl; j++){
                masks[i] |= 1 << (word[j] - 'a');
            }
        }

        int maxProd = 0;
        for(int i=0; i<length; i++){
            for(int j=i+1; j<length; j++){
                if((masks[i] & masks[j]) == 0){
                    maxProd = max(maxProd, int(words[i].size() * words[j].size()));
                }
            }
        }

        return maxProd;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

通过位运算解决

vector<int>masks(length);

        for(int i=0; i<length; i++){
            string word = words[i];

            int wordl = word.size();
            for(int j=0; j<wordl; j++){
                masks[i] |= 1 << (word[j] - 'a');
            }
        }
1
2
3
4
5
6
7
8
9
10

将字符串转二进制