318. Maximum Product of Word Lengths

I used bucket to hash the letters in first place but I got the TLE.

1:  class Solution {  
2:  public:  
3:    int maxProduct(vector<string>& words) {  
4:      unordered_map<string, vector<int>> mp;  
5:      for (int i = 0; i < words.size(); i++) {  
6:        vector<int> bucket(26, 0);  
7:        for (int j = 0; j < words[i].size(); j++) {  
8:          bucket[words[i][j]-'a'] = 1;  
9:        }  
10:        mp[words[i]] = bucket;  
11:      }  
12:      int res = 0;  
13:      for (int i = 0; i < words.size(); i++) {  
14:        for (int j = i+1; j < words.size(); j++) {  
15:          int k = 0;  
16:          for (; k < 26; k++) {  
17:            if (mp[words[i]][k] && mp[words[j]][k]) break;  
18:          }  
19:          if (k == 26) res = max(res, (int)words[i].size() * (int)words[j].size());  
20:        }  
21:      }  
22:      return res;  
23:    }  
24:  };  

A trick here is the problem explicitly says that all letters in the words will be low case. Since there are 26 letters, we can use integer which has 32bits as a letter mask for each word.

1:  class Solution {  
2:  public:  
3:    int maxProduct(vector<string>& words) {  
4:      vector<int> masks(words.size(), 0);  
5:      for (int i = 0; i < words.size(); i++) {  
6:        for (int j = 0; j < words[i].size(); j++) {  
7:          masks[i] |= 1 << (words[i][j]-'a');  
8:        }  
9:      }  
10:      int res = 0;  
11:      for (int i = 0; i < words.size(); i++) {  
12:        for (int j = 0; j < i; j++) {  
13:          if (!(masks[i] & masks[j])) {  
14:            res = max(res, (int)(words[i].size()*words[j].size()));  
15:          }  
16:        }  
17:      }  
18:      return res;  
19:    }  
20:  };