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.
1function subdomainVisits(cpdomains) {
2 let counts = {};
3 cpdomains.forEach(cpdomain => {
4 let [count, domain] = cpdomain.split(' ');
5 count = parseInt(count);
6
7 let fragments = domain.split('.');
8
9 for (let i = 0; i < fragments.length; i++) {
10 let subdomain = fragments.slice(i).join('.');
11 counts[subdomain] = (counts[subdomain] || 0) + count;
12 }
13 });
14
15 let result = [];
16 for (let domain in counts) {
17 result.push(`${counts[domain]} ${domain}`);
18 }
19
20 return result;
21}
22
23let cpdomains = ["9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"];
24let result = subdomainVisits(cpdomains);
25result.forEach(res => console.log(res));The JavaScript code uses an object to track domain visit counts. By iterating through each domain, it utilizes string operations to determine and update subdomain counts.
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.