What is the best approach to solve the Subdomain Visit Count problem?

The most efficient approach involves using array scanning to break down each domain into its subdomains and counting visits with a hash map.

How do I handle domains with different levels of subdomains?

Ensure that you account for all subdomains from the most specific to the least specific, updating the visit counts for each parent domain.

What should I do if I encounter duplicate subdomains?

Accumulate the visit counts for duplicate subdomains using a hash map, ensuring the final count includes all visits from all occurrences.

Can I return the result in any order?

Yes, the problem statement allows returning the result in any order, as long as the visit counts for each subdomain are correct.

How does the Subdomain Visit Count problem relate to other string manipulation problems?

It requires breaking down and processing strings (domains), but with an added complexity of counting and handling nested structures through subdomains.

#811

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

子域名访问计数

网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ，二级域名为 "leetcode.com" ，最低一级为 "discuss.leetcode.com" 。当访问域名 "discuss.leetcode.com" 时，同时也会隐式访问其父域名 "lee…

数组哈希表字符串计数

题目描述

网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ，二级域名为 "leetcode.com" ，最低一级为 "discuss.leetcode.com" 。当访问域名 "discuss.leetcode.com" 时，同时也会隐式访问其父域名 "leetcode.com" 以及 "com" 。

计数配对域名 是遵循 "rep d1.d2.d3" 或 "rep d1.d2" 格式的一个域名表示，其中 rep 表示访问域名的次数，d1.d2.d3 为域名本身。

例如，"9001 discuss.leetcode.com" 就是一个 计数配对域名 ，表示 discuss.leetcode.com 被访问了 9001 次。

给你一个 计数配对域名 组成的数组 cpdomains ，解析得到输入中每个子域名对应的 计数配对域名 ，并以数组形式返回。可以按 任意顺序 返回答案。

示例 1：

输入：cpdomains = ["9001 discuss.leetcode.com"]
输出：["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
解释：例子中仅包含一个网站域名："discuss.leetcode.com"。
按照前文描述，子域名 "leetcode.com" 和 "com" 都会被访问，所以它们都被访问了 9001 次。

示例 2：

输入：cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输出：["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
解释：按照前文描述，会访问 "google.mail.com" 900 次，"yahoo.com" 50 次，"intel.mail.com" 1 次，"wiki.org" 5 次。
而对于父域名，会访问 "mail.com" 900 + 1 = 901 次，"com" 900 + 50 + 1 = 951 次，和 "org" 5 次。

提示：

1 <= cpdomain.length <= 100
1 <= cpdomain[i].length <= 100
cpdomain[i] 会遵循 "rep_i d1_i.d2_i.d3_i" 或 "rep_i d1_i.d2_i" 格式
rep_i 是范围 [1, 10⁴] 内的一个整数
d1_i、d2_i 和 d3_i 由小写英文字母组成

lightbulb

解题思路

方法一：哈希表

我们用哈希表 cnt 存储每个域名（子域名）对应的访问次数。

然后遍历数组，对于每个域名，我们将其拆分为子域名，然后更新哈希表 cnt 中对应的访问次数。

最后，我们将哈希表中的键值对转换为数组，即可得到答案。

时间复杂度 $O(L)$ ，空间复杂度 $O(L)$ 。其中 $L$ 是数组 cpdomains 中所有域名的长度之和。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        cnt = Counter()
        for s in cpdomains:
            v = int(s[: s.index(' ')])
            for i, c in enumerate(s):
                if c in ' .':
                    cnt[s[i + 1 :]] += v
        return [f'{v} {s}' for s, v in cnt.items()]

speed

复杂度分析

指标	值
时间	O(n \cdot m)
空间	O(n \cdot m)

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient handling of both domain parsing and counting subdomains.
question_mark
Ensure the candidate uses an appropriate data structure for counting subdomains (like a hash map).
question_mark
Test the candidate's understanding of subdomain hierarchy and handling nested domains.

warning

常见陷阱

外企场景

error
Failing to account for all subdomains of a given domain, including its parent domains.
error
Incorrectly managing the subdomain hierarchy, leading to missing visit counts for certain subdomains.
error
Not handling cases where multiple domains share the same subdomain.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider handling cases with very large input sizes, ensuring the solution scales efficiently.
arrow_right_alt
Test cases with varying domain levels (e.g., some domains with three parts, others with two).
arrow_right_alt
Edge cases where a domain has no subdomains.

help

常见问题

外企场景

继续练习

#692 前K个高频单词 #1366 通过投票对团队排名 #1684 统计一致字符串的数目