LeetCode 811 Subdomain Visit Count

LeetCode

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 "rep<sub>i</sub> d1<sub>i</sub>.d2<sub>i</sub>.d3<sub>i</sub>" format or the "rep<sub>i</sub> d1<sub>i</sub>.d2<sub>i</sub>" format.
rep<sub>i</sub> is an integer in the range [1, 10<sup>4</sup>]. d1<sub>i</sub>, d2<sub>i</sub>, and d3<sub>i</sub> consist of lowercase English letters.

题目大意：

统计所以domain和子域名个数

解题思路：

遍历每个domain，将domain和个数存入dict，再对domain按点号break，将每个sub-domain存入dict

解题步骤：

N/A

注意事项：

1. Line 64根据题意倒转统计，Line 65记得非空时候加点号

Python代码：

def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
	domain_to_count = collections.defaultdict(int)
	for pair_str in cpdomains:
		pair = pair_str.split(' ')
		count = int(pair[0])
		domain = pair[1]
		subdomain = ''
		for segment in domain.split('.')[::-1]:
			subdomain = segment + ('.' + subdomain if subdomain else '')
			domain_to_count[subdomain] += count
	return ['{} {}'.format(_count, _domain) for _domain, _count in domain_to_count.items()]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)