Subdomain Visit Count - Leetcode Solution

Problem statement:

You are given a list of website domain strings cpdomains and their respective count. For example, ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]. Now, you are required to compute the sum of count of each website domain along with all sub-domains that it contains. For example, visit count for "mail.com" is the sum of "intel.mail.com" and "google.mail.com", and visit count for "google.mail.com" is "900".

Solution:

This problem can be solved using a dictionary to store the count of each sub-domain. We will iterate over each element in the given list cpdomains. For each element, we will extract the count and the domain, and then split the domain by "." to get all the subdomains.

We will then iterate over all the subdomains and create a key-value pair in the dictionary where the key is the subdomain and the value is the count of the domain. If the subdomain already exists in the dictionary, we will increment its count by the count of the current domain.

Finally, we will iterate over all the key-value pairs in the dictionary and add the value to the result sum.

Here is the python implementation of this approach:

def subdomainVisits(cpdomains: List[str]) -> List[str]:
    counts = {}
    for domain in cpdomains:
        count, domain = domain.split()
        count = int(count)
        subdomains = domain.split(".")
        for i in range(len(subdomains)):
            subdomain = ".".join(subdomains[i:])
            if subdomain not in counts:
                counts[subdomain] = count
            else:
                counts[subdomain] += count
    
    result = []
    for subdomain, count in counts.items():
        result.append(str(count) + " " + subdomain)
    
    return result

Complexity Analysis:

• Time Complexity: O(N*M) where N is the number of domains and M is the maximum number of subdomains in a domain.
• Space Complexity: O(N*M) as we are storing each subdomain in the dictionary.

1