Subdomain Visit Count

Published: Sep 24, 2022

Medium Counting String Hash Table

Introduction

As the title shows, this is a counting problem. The hash table is a good data structure to save subdomain name and count pairs. While counting, the given domain name should be divided first, then concatenate next in reverse order. How to concatenate might need a bit of consideration.

Problem Description

A website domain "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com" and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" and "com" implicitly.

A count-paired domain is a domain that has one of the two formats "rep d1.d2.d3" or "rep d1.d2" where rep is the number of visits to the domain and d1.d2.d3 is the domain itself.

  • For example, "9001 discuss.leetcode.com" is a count-paired domain that indicates that discuss.leetcode.com was visited 9001 times.

Given an array of count-paired domains cpdomains, return an array of the count-paired domains of each subdomain in the input. You may return the answer in any order.

Constraints:

  • 1 <= cpdomain.length <= 100
  • 1 <= cpdomain[i].length <= 100
  • cpdomain[i] follows either the "repi d1i.d2i.d3i" format or the "repi d1i.d2i" format.
  • rep[i] is an integer in the range [1, 104].
  • d1[i], d2[i], and d3[i] consist of lowercase English letters.

https://leetcode.com/problems/subdomain-visit-count/

Examples

Example 1
Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]

Example 2
Input: cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output: ["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]

Analysis

Each string should be divided by a space, then dot. The subdomain fragments will be concatenated in reverse order: com, leetcode.com, discuss.leetcode.com. Add count in all of concatenated subdomains. Finally, hash table key-value pairs should be converted to strings.

Solution

class SubdomainVisitCount:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        domains = collections.defaultdict(int)
        for cpdomain in cpdomains:
            cnt, domain = cpdomain.split(' ')
            cnt = int(cnt)
            names = domain.split('.')
            ns = names[-1]
            for i in range(len(names) - 2, -1, -1):
                domains[ns] += cnt
                ns = '.'.join([names[i], ns])
            domains[ns] += cnt
        return ['%s %s' % (v, k) for k, v in domains.items()]

Complexities

  • Time: O(n)
  • Space: O(n)