leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0318.cpp (1141B)

      1 class Solution {
      2   public:
      3     int maxProduct(const vector<string> &words) {
      4         static uint32_t masks[1001];
      5 
      6         int res = 0;
      7         for (int i = 0; i < words.size(); i++) {
      8             uint32_t mask = 0;
      9             for (const char c : words[i])
     10                 mask |= 1 << (c & 0x1F);
     11             masks[i] = mask;
     12             for (int j = 0; j < i; j++) {
     13                 if ((masks[i] & masks[j]) == 0) {
     14                     res = max(res, (int)(words[i].size() * words[j].size()));
     15                 }
     16             }
     17         }
     18 
     19         return res;
     20     }
     21 };
     22 
     23 class Solution {
     24   public:
     25     int maxProduct(const vector<string> &words) {
     26         unordered_map<int, int> um;
     27 
     28         int res = 0;
     29         for (int i = 0; i < words.size(); i++) {
     30             uint32_t mask = 0;
     31             for (const char c : words[i])
     32                 mask |= 1 << (c & 0x1F);
     33             um[mask] = max(um[mask], (int)words[i].size());
     34         }
     35 
     36         for (const auto [k1, v1] : um) {
     37             for (const auto [k2, v2] : um) {
     38                 if ((k1 & k2) == 0) res = max(res, v1 * v2);
     39             }
     40         }
     41 
     42         return res;
     43     }
     44 };