Skip to content

811. Subdomain Visit Count

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  vector<string> subdomainVisits(vector<string>& cpdomains) {
    vector<string> ans;
    unordered_map<string, int> count;

    for (const string& cpdomain : cpdomains) {
      const int space = cpdomain.find(' ');
      const int num = stoi(cpdomain.substr(0, space));
      const string& domain = cpdomain.substr(space + 1);
      count[domain] += num;
      for (int i = 0; i < domain.length(); ++i)
        if (domain[i] == '.')
          count[domain.substr(i + 1)] += num;
    }

    for (const auto& [subdomain, freq] : count)
      ans.push_back(to_string(freq) + ' ' + subdomain);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public List<String> subdomainVisits(String[] cpdomains) {
    List<String> ans = new ArrayList<>();
    Map<String, Integer> count = new HashMap<>();

    for (final String cpdomain : cpdomains) {
      final int space = cpdomain.indexOf(' ');
      final int num = Integer.valueOf(cpdomain.substring(0, space));
      final String domain = cpdomain.substring(space + 1);
      count.merge(domain, num, Integer::sum);
      for (int i = 0; i < domain.length(); ++i)
        if (domain.charAt(i) == '.') {
          String subdomain = domain.substring(i + 1);
          count.merge(subdomain, num, Integer::sum);
        }
    }

    for (final String subdomain : count.keySet())
      ans.add(String.valueOf(count.get(subdomain)) + ' ' + subdomain);

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
    ans = []
    count = collections.Counter()

    for cpdomain in cpdomains:
      num, domains = cpdomain.split()
      num, domains = int(num), domains.split('.')
      for i in reversed(range(len(domains))):
        count['.'.join(domains[i:])] += num

    return [str(freq) + ' ' + domain for domain, freq in count.items()]