Problem

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 thecount-paired domains of each subdomain in the input. You may return the answer in any order.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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, 10^4].
  • d1i, d2i, and d3i consist of lowercase English letters.

Solution

Method 1 - Hash Map for Subdomain Counting

Intuition

For each domain, split it into all possible subdomains and accumulate the visit counts for each. Use a hash map to store the counts.

Approach

  1. For each string in cpdomains, split into count and domain.
  2. For each subdomain (by splitting at each .), add the count to the hash map.
  3. Return the result as a list of strings in the required format.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> count;
        for (auto& s : cpdomains) {
            int i = s.find(' ');
            int c = stoi(s.substr(0, i));
            string domain = s.substr(i+1);
            for (int j = 0; j < domain.size(); ++j) {
                if (j == 0 || domain[j-1] == '.') {
                    count[domain.substr(j)] += c;
                }
            }
        }
        vector<string> res;
        for (auto& [d, c] : count) res.push_back(to_string(c) + " " + d);
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import "strconv"
import "strings"
func subdomainVisits(cpdomains []string) []string {
    count := map[string]int{}
    for _, s := range cpdomains {
        parts := strings.SplitN(s, " ", 2)
        c, _ := strconv.Atoi(parts[0])
        domain := parts[1]
        for i := 0; i < len(domain); i++ {
            if i == 0 || domain[i-1] == '.' {
                count[domain[i:]] += c
            }
        }
    }
    res := []string{}
    for d, c := range count {
        res = append(res, strconv.Itoa(c)+" "+d)
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;
class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> count = new HashMap<>();
        for (String s : cpdomains) {
            String[] parts = s.split(" ");
            int c = Integer.parseInt(parts[0]);
            String domain = parts[1];
            for (int i = 0; i < domain.length(); ++i) {
                if (i == 0 || domain.charAt(i-1) == '.') {
                    count.put(domain.substring(i), count.getOrDefault(domain.substring(i), 0) + c);
                }
            }
        }
        List<String> res = new ArrayList<>();
        for (String d : count.keySet())
            res.add(count.get(d) + " " + d);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

fun subdomainVisits(cpdomains: Array<String>): List<String> {
    val count = mutableMapOf<String, Int>()
    for (s in cpdomains) {
        val (c, domain) = s.split(" ", limit=2)
        val cnt = c.toInt()
        for (i in domain.indices) {
            if (i == 0 || domain[i-1] == '.')
                count[domain.substring(i)] = count.getOrDefault(domain.substring(i), 0) + cnt
        }
    }
    return count.map { "${it.value} ${it.key}" }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def subdomainVisits(cpdomains):
    count = {}
    for s in cpdomains:
        c, domain = s.split()
        c = int(c)
        for i in range(len(domain)):
            if i == 0 or domain[i-1] == '.':
                sub = domain[i:]
                count[sub] = count.get(sub, 0) + c
    return [f"{v} {d}" for d, v in count.items()]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

use std::collections::HashMap;
pub fn subdomain_visits(cpdomains: Vec<String>) -> Vec<String> {
    let mut count = HashMap::new();
    for s in cpdomains.iter() {
        let mut it = s.splitn(2, ' ');
        let c: i32 = it.next().unwrap().parse().unwrap();
        let domain = it.next().unwrap();
        for (i, ch) in domain.char_indices() {
            if i == 0 || domain.as_bytes()[i-1] == b'.' {
                *count.entry(domain[i..].to_string()).or_insert(0) += c;
            }
        }
    }
    count.into_iter().map(|(d, v)| format!("{} {}", v, d)).collect()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function subdomainVisits(cpdomains: string[]): string[] {
    const count: Record<string, number> = {};
    for (const s of cpdomains) {
        const [c, domain] = s.split(' ');
        const cnt = parseInt(c);
        for (let i = 0; i < domain.length; i++) {
            if (i === 0 || domain[i-1] === '.') {
                const sub = domain.slice(i);
                count[sub] = (count[sub] || 0) + cnt;
            }
        }
    }
    return Object.entries(count).map(([d, v]) => `${v} ${d}`);
}

Complexity

  • ⏰ Time complexity: O(N*L) where N is the number of domains and L is the average length
  • 🧺 Space complexity: O(N*L)