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.
1import java.util.*;
2
3public class Solution {
4 public static List<String> subdomainVisits(String[] cpdomains) {
5 Map<String, Integer> counts = new HashMap<>();
6 for (String cpdomain : cpdomains) {
7 String[] parts = cpdomain.split(" ");
8 int count = Integer.parseInt(parts[0]);
9 String domain = parts[1];
10 while (true) {
11 counts.put(domain, counts.getOrDefault(domain, 0) + count);
12 int dotIndex = domain.indexOf('.');
13 if (dotIndex == -1) break;
14 domain = domain.substring(dotIndex + 1);
15 }
16 }
17 List<String> result = new ArrayList<>();
18 for (Map.Entry<String, Integer> entry : counts.entrySet()) {
19 result.add(entry.getValue() + " " + entry.getKey());
20 }
21 return result;
22 }
23
24 public static void main(String[] args) {
25 String[] cpdomains = {"9001 discuss.leetcode.com", "900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"};
26 List<String> result = subdomainVisits(cpdomains);
27 for (String res : result) {
28 System.out.println(res);
29 }
30 }
31}The Java method `subdomainVisits` reads the count-paired domains, splits each domain, and uses a HashMap to tally the counts for each subdomain. It processes domains incrementally by changing substring scopes and accumulates total results for all domains.
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.
1import
Java uses a nested hash map (Trie) to collect domains. With recursive DFS, subdomains are gathered from nodes post-insertion, forming a result list.