Introduction

In this blog post, we will explore how to solve the LeetCode problem "811" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: cpdomains = ["9001 discuss.leetcode.com"] Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"] Explanation: We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times. 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"] Explanation: We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times. 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. repi is an integer in the range [1, 104]. d1i, d2i, and d3i consist of lowercase English letters.

Explanation

• Parse and Aggregate: Iterate through the input cpdomains. For each domain, split the string into count and domain name. Then, iteratively generate subdomains from the full domain.
  • Count Occurrences: Use a hash map (dictionary) to store the count for each subdomain. If a subdomain already exists, add the new count to the existing count.
  • Format Output: Finally, iterate through the hash map and format the output into the required "count domain" string format.

• Runtime Complexity: O(N*M), where N is the number of domains in the input array and M is the maximum number of subdomains in a single domain string (at most 3). Storage Complexity: O(K), where K is the number of unique subdomains.

Code

    def subdomainVisits(cpdomains):
    """
    Calculates the count-paired domains of each subdomain in the input.

    Args:
        cpdomains: A list of count-paired domains.

    Returns:
        A list of count-paired domains of each subdomain.
    """

    domain_counts = {}
    for cpdomain in cpdomains:
        count, domain = cpdomain.split()
        count = int(count)
        domains = domain.split('.')

        for i in range(len(domains)):
            subdomain = '.'.join(domains[i:])
            if subdomain in domain_counts:
                domain_counts[subdomain] += count
            else:
                domain_counts[subdomain] = count

    result = [str(count) + ' ' + domain for domain, count in domain_counts.items()]
    return result