Sponsored
Sponsored
We will use a hashmap (or dictionary) to record the visit count of each subdomain as we process each count-paired domain in the input list. By splitting each domain into its subdomains, starting from the rightmost part, we accumulate the visits to each subdomain in the map.
Time Complexity: O(n * m) where n is the number of domains and m is the average number of subcomponents of a domain. Space Complexity: O(n * m) for storing subdomains in the map.
1#include <iostream>
2#include <vector>
3#include <string>
4#include <map>
5
6using namespace std;
7
8vector<string> subdomainVisits(vector<string>& cpdomains) {
9 map<string, int> counts;
10 for (const string &cpdomain : cpdomains) {
11 int pos = cpdomain.find(' ');
12 int count = stoi(cpdomain.substr(0, pos));
13 string domain = cpdomain.substr(pos + 1);
14
15 while (true) {
16 counts[domain] += count;
17 size_t next_pos = domain.find('.');
18 if (next_pos == string::npos) break;
19 domain = domain.substr(next_pos + 1);
20 }
21 }
22
23 vector<string> result;
24 for (const auto &entry : counts) {
25 result.push_back(to_string(entry.second) + " " + entry.first);
26 }
27 return result;
28}
29
30int main() {
31 vector<string> cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
32 vector<string> result = subdomainVisits(cpdomains);
33 for (const string &res : result) {
34 cout << res << endl;
35 }
36 return 0;
37}This solution uses a std::map to accumulate the visits for each subdomain. By iterating over the input domains, extracting the count and domain, and recursively breaking down each domain into subdomains, it accumulates counts in the map.
We can also implement the solution using a trie structure to track domains. Each subcomponent of a domain traverses down nodes in the trie, updating the count at each node. This approach leverages the natural hierarchy of domains efficiently through a tree structure.
Time Complexity: O(n * m), n domains and m depth. Space Complexity: Higher space use due to node allocations.
1
JavaScript Trie utilizes nested objects and various array operations to derive and craft subdomains hierarchically managing counts and constructing output.