grid47 Exploring patterns and algorithms
Aug 17, 2024
6 min read
Solution to LeetCode 811: Subdomain Visit Count Problem
You are given a list of count-paired domains, where each entry consists of a number followed by a domain name. The number represents the number of visits to that domain. A domain may also have subdomains, and visiting a subdomain also counts as visiting its parent domains. Your task is to return the count of visits for each domain and its subdomains.
Problem
Approach
Steps
Complexity
Input: You will be provided with a list of strings where each string contains a visit count and a domain name. The format is 'count domain'. Each domain name can have subdomains separated by dots.
• Explanation: In this example, 'xyz.com' is visited 100 times, 'abc.xyz.com' is visited 200 times, and 'com' is visited a total of 300 times (100 from 'xyz.com' and 200 from 'abc.xyz.com').
Approach: The approach involves counting the number of visits for each domain and all its subdomains by iterating through the input list and breaking down the domain names into their subdomains.
Observations:
• Each domain name can have multiple subdomains.
• The number of visits to the parent domain is shared by all of its subdomains.
• We need to keep track of visits to both the full domain and all possible subdomains.
Steps:
• For each domain in the input list, split the domain by '.' to identify the subdomains.
• For each subdomain, update the visit count for that subdomain and its parent domains.
• Store the visit counts in a map or dictionary and return the results in the required format.
Empty Inputs:
• If the input list is empty, return an empty result.
Large Inputs:
• Ensure that the solution can handle the upper limit of the input size efficiently.
Special Values:
• Check how the solution handles cases where subdomains are not repeated.
Constraints:
• The solution should run efficiently for the maximum number of domains.
vector<string> subdomainVisits(vector<string>& cpdomains) {
unordered_map<string, int> count;
for(autocp: cpdomains) {
int i = cp.find(" ");
int n = stoi(cp.substr(0, i));
string s = cp.substr(i +1);
for(int i =0; i < s.size(); i++) {
if(s[i] =='.')
count[s.substr(i +1)] += n;
}
count[s] += n;
}
vector<string> res;
for(autoit: count)
res.push_back(to_string(it.second) +" "+ it.first);
return res;
}
This is the function signature, defining a function `subdomainVisits` that takes a vector of strings (`cpdomains`). The function returns a vector of strings containing the subdomain visit counts.
2 : Variable Initialization
unordered_map<string, int> count;
An unordered map `count` is initialized to store the number of visits to each subdomain. The keys are subdomains and the values are visit counts.
3 : Subdomain Extraction
for(autocp: cpdomains) {
The function begins a loop to process each domain in the `cpdomains` list.
4 : Substring Processing
int i = cp.find(" ");
This line finds the first space in the string `cp` which separates the visit count from the domain.
5 : String to Integer Conversion
int n = stoi(cp.substr(0, i));
This converts the numeric part of the string (before the space) into an integer `n`, representing the number of visits.
6 : Domain Extraction
string s = cp.substr(i +1);
The part of the string after the space is extracted and stored in `s`, which is the full domain name.
7 : Loop through Subdomains
for(int i =0; i < s.size(); i++) {
This inner loop iterates over each character in the domain string `s`.
8 : Subdomain Counting
if(s[i] =='.')
Whenever a period (`.`) is encountered, it indicates the end of a subdomain. The part after the period is treated as a subdomain.
9 : Increment Subdomain Count
count[s.substr(i +1)] += n;
The subdomain starting from the current position is added to the `count` map, and its count is incremented by `n`.
10 : Final Count Update
count[s] += n;
The full domain `s` is also added to the map with its count incremented by `n`.
11 : Result Vector Initialization
vector<string> res;
A new vector `res` is initialized to store the result.
12 : Result Population
for(autoit: count)
This loop iterates over the `count` map to prepare the result vector by formatting the counts.
Each entry in `count` is formatted as a string with the visit count and the domain, and added to the result vector.
14 : Return Result
return res;
The result vector `res` is returned, containing the formatted subdomain visit counts.
Best Case: O(n) where n is the total number of domains.
Average Case: O(n * m) where n is the number of input domains and m is the average number of subdomains per domain.
Worst Case: O(n * m) in the worst case when every domain has many subdomains.
Description: The time complexity mainly depends on the number of subdomains and how we iterate through them.
Best Case: O(n) when there are fewer subdomains.
Worst Case: O(n * m) where n is the number of domains and m is the average number of subdomains, due to the space used by the map to store the visit counts.
Description: The space complexity is determined by the number of unique subdomains that need to be stored.
