algoadvance

Leetcode 811. Subdomain Visit Count

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”. Given a list of count-paired domains, we need to count the number of visits to each subdomain.

For example, a count-paired domain “9001 discuss.leetcode.com” might represent that discuss.leetcode.com received 9001 visits. We should split this into:

Function Signature:

vector<string> subdomainVisits(vector<string>& cpdomains);

Clarifying Questions

  1. Input Format:
    • Is each input string in the form “count domain” where count is an integer and domain is a string with lower-case letters and periods?
    • Can the number of domain entries be very large?
  2. Output Format:
    • Should the output be in any specific order?
  3. Domain Format:
    • Are we guaranteed that list elements are well-formed according to the problem statement?

Strategy

  1. Initialize a hashmap (unordered_map) to store the counts of each subdomain.
  2. Iterate over each domain string in the input list.
  3. For each domain string, extract the count and the full domain.
  4. Split the domain into its subdomains.
  5. For each subdomain, update its count in the hashmap.
  6. After processing all inputs, construct the output list from the hashmap.

Code

Here is the C++ implementation:

#include <vector>
#include <string>
#include <sstream>
#include <unordered_map>
using namespace std;

vector<string> subdomainVisits(vector<string>& cpdomains) {
    unordered_map<string, int> domainCount;
    
    for (const string& cpdomain : cpdomains) {
        // Split into count and domain
        stringstream ss(cpdomain);
        string countStr, domain;
        ss >> countStr >> domain;
        int count = stoi(countStr);
        
        // Process the domain and its subdomains
        vector<string> subdomains;
        size_t pos = 0;
        while ((pos = domain.find('.')) != string::npos) {
            subdomains.push_back(domain);
            domain = domain.substr(pos + 1);
        }
        // Push the last part
        subdomains.push_back(domain);
        
        // Update counts in the unordered_map
        for (const string& subdomain : subdomains) {
            domainCount[subdomain] += count;
        }
    }
    
    // Construct the result from the domainCount map
    vector<string> result;
    for (const auto& entry : domainCount) {
        result.push_back(to_string(entry.second) + " " + entry.first);
    }
    
    return result;
}

Explanation

  1. Splitting the count and domain: We use stringstream to split the input string into count and domain.
  2. Extracting Subdomains: We use a loop to split the domain into all possible subdomains and store them in a vector.
  3. Updating Counts: We update the count of each subdomain in our unordered_map.
  4. Constructing Result: Finally, we create the result vector by converting the items from the unordered_map into the requested format.

Time Complexity

The time complexity is (O(N \cdot M)) where:

Each domain string is processed independently, and within each string, handling the subdomain splits and hashmap updates are efficient operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI