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.
1def subdomainVisits(cpdomains):
2 counts = {}
3 for cpdomain in cpdomains:
4 count, domain = cpdomain.split()
5 count = int(count)
6 fragments = domain.split('.')
7 for i in range(len(fragments)):
8 subdomain = '.'.join(fragments[i:])
9 counts[subdomain] = counts.get(subdomain, 0) + count
10 return [f"{count} {domain}" for domain, count in counts.items()]
11
12cpdomains = ["9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
13result = subdomainVisits(cpdomains)
14for item in result:
15 print(item)The Python implementation in `subdomainVisits` splits each domain into its subdomains and updates a dictionary with the counts for each subdomain. The result is constructed out of this dictionary.
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#include <map>
#include <vector>
#include <sstream>
using namespace std;
struct TrieNode {
map<string, TrieNode*> children;
int count = 0;
};
void insert(TrieNode* root, vector<string>& tokens, int count) {
TrieNode* node = root;
for (auto it = tokens.rbegin(); it != tokens.rend(); ++it) {
if (!node->children[*it])
node->children[*it] = new TrieNode();
node = node->children[*it];
node->count += count;
}
}
void dfs(TrieNode* node, string current, vector<string>& result) {
if (node->count > 0) {
result.push_back(to_string(node->count) + " " + current);
}
for (auto& child : node->children) {
dfs(child.second, child.first + (current.empty() ? "" : ".") + current, result);
}
}
vector<string> subdomainVisits(vector<string>& cpdomains) {
TrieNode* root = new TrieNode();
for (auto& domain : cpdomains) {
stringstream ss(domain);
int count;
ss >> count;
string dom;
ss >> dom;
vector<string> tokens;
stringstream ss_tokens(dom);
string token;
while (getline(ss_tokens, token, '.')) {
tokens.push_back(token);
}
insert(root, tokens, count);
}
vector<string> result;
dfs(root, "", result);
return result;
}
int main() {
vector<string> cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
vector<string> result = subdomainVisits(cpdomains);
for (string& s : result) {
cout << s << endl;
}
return 0;
}This solution leverages a trie to efficiently store subdomain structures. Each visit parses the input domain into segments, which are inserted into the trie, incrementing counts at each node. A recursive DFS then builds results by aggregating counts.