leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2306.cpp (1424B)

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