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.
1A Trie implementation in C would involve struct definitions for nodes, containing a map to child nodes and an integer to tally counts.