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.
1using System;
2using System.Collections.Generic;
3
4class Solution {
5 public static IList<string> SubdomainVisits(string[] cpdomains) {
6 Dictionary<string, int> counts = new Dictionary<string, int>();
7 foreach (string cpdomain in cpdomains) {
8 string[] parts = cpdomain.Split(' ');
9 int count = int.Parse(parts[0]);
10 string domain = parts[1];
11
12 while (true) {
13 if (counts.ContainsKey(domain)) {
14 counts[domain] += count;
15 } else {
16 counts[domain] = count;
17 }
18
19 int dotIndex = domain.IndexOf('.');
20 if (dotIndex < 0) break;
21 domain = domain.Substring(dotIndex + 1);
22 }
23 }
24
25 List<string> result = new List<string>();
26 foreach (KeyValuePair<string, int> entry in counts) {
27 result.Add(entry.Value + " " + entry.Key);
28 }
29 return result;
30 }
31
32 public static void Main(string[] args) {
33 string[] cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
34 IList<string> result = SubdomainVisits(cpdomains);
35 foreach (string res in result) {
36 Console.WriteLine(res);
37 }
38 }
39}This C# program processes each domain, storing subdomain visit counts in a Dictionary. As subdomains are updated with their counts, they get added to the result list which is finally printed.
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
Similar to Java, Python's Trie insertion and depth-first search traverses and links domain parts into nodes to form valid subdomains and results after parsing input strings aptly.