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.
1#include <iostream>
#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.