leetcode

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

2306.cpp (1424B)

      1 // Group by first letter, 637ms
      2 class Solution {
      3   public:
      4     long long distinctNames(vector<string> &ideas) {
      5         array<unordered_set<string>, 26> um;
      6         for (const auto &idea : ideas)
      7             um[idea.front() - 'a'].insert(idea.substr(1));
      8 
      9         long long res = 0ll;
     10         for (int i = 0; i < 26; i++) {
     11             for (int j = i + 1; j < 26; j++) {
     12                 long long c1 = 0ll, c2 = 0ll;
     13                 for (const auto &s : um[i])
     14                     c1 += !um[j].count(s);
     15                 for (const auto &s : um[j])
     16                     c2 += !um[i].count(s);
     17                 res += c1 * c2;
     18             }
     19         }
     20 
     21         return res * 2;
     22     }
     23 };
     24 
     25 // Group by suffix, 373ms
     26 class Solution {
     27   public:
     28     long long distinctNames(vector<string> &ideas) {
     29         unordered_map<string, bitset<32>> um;
     30         unordered_map<bitset<32>, int> cnt;
     31 
     32         for (const auto &idea : ideas)
     33             um[idea.substr(1)].set(idea.front() - 'a');
     34         for (const auto &[k, v] : um)
     35             cnt[v]++;
     36 
     37         long long res = 0ll;
     38         for (auto it1 = cnt.begin(); it1 != cnt.end(); it1++) {
     39             for (auto it2 = next(it1); it2 != cnt.end(); it2++) {
     40                 int same = (it1->first & it2->first).count();
     41                 res += (it2->first.count() - same) * (it1->first.count() - same) * it1->second * it2->second;
     42             }
     43         }
     44 
     45         return res * 2;
     46     }
     47 };