Medium

题目描述

网站域名 “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 <= cpdomains.length <= 100
  • 1 <= cpdomains[i].length <= 100
  • cpdomains[i] 会遵循 “repi d1i.d2i.d3i” 或 “repi d1i.d2i” 格式
  • repi 是范围 [1, 10^4] 内的整数
  • d1i、d2i 和 d3i 由小写英文字母组成

解题思路

解题思路

这是一个典型的字符串处理和哈希表计数问题。核心思路是：

  1. 解析输入：对每个计数配对域名，分离出访问次数和完整域名
  2. 提取子域名：从完整域名中提取所有可能的子域名（包括自身）
  3. 累计计数：使用哈希表记录每个子域名的总访问次数
  4. 格式化输出：将哈希表中的结果转换为要求的格式

关键步骤：

  • 对于域名 “discuss.leetcode.com”，需要提取的子域名有：
    • “discuss.leetcode.com”（完整域名）
    • “leetcode.com”（去掉第一部分）
    • “com”（顶级域名）

实现方法：

  • 使用字符串分割获取访问次数和域名
  • 通过查找 “.” 的位置来逐步提取子域名
  • 使用哈希表累计每个子域名的访问次数

时间复杂度主要取决于处理所有域名字符串的总长度，空间复杂度取决于不同子域名的数量。

代码实现

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> count;
        
        for (const string& domain : cpdomains) {
            int spacePos = domain.find(' ');
            int visits = stoi(domain.substr(0, spacePos));
            string fullDomain = domain.substr(spacePos + 1);
            
            // 添加完整域名
            count[fullDomain] += visits;
            
            // 添加所有子域名
            for (int i = 0; i < fullDomain.length(); i++) {
                if (fullDomain[i] == '.') {
                    string subdomain = fullDomain.substr(i + 1);
                    count[subdomain] += visits;
                }
            }
        }
        
        vector<string> result;
        for (const auto& pair : count) {
            result.push_back(to_string(pair.second) + " " + pair.first);
        }
        
        return result;
    }
};

class Solution:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        count = {}
        
        for domain in cpdomains:
            visits, full_domain = domain.split(' ', 1)
            visits = int(visits)
            
            # 添加完整域名
            count[full_domain] = count.get(full_domain, 0) + visits
            
            # 添加所有子域名
            for i in range(len(full_domain)):
                if full_domain[i] == '.':
                    subdomain = full_domain[i + 1:]
                    count[subdomain] = count.get(subdomain, 0) + visits
        
        return [f"{visits} {domain}" for domain, visits in count.items()]

public class Solution {
    public IList<string> SubdomainVisits(string[] cpdomains) {
        var count = new Dictionary<string, int>();
        
        foreach (string domain in cpdomains) {
            int spaceIndex = domain.IndexOf(' ');
            int visits = int.Parse(domain.Substring(0, spaceIndex));
            string fullDomain = domain.Substring(spaceIndex + 1);
            
            // 添加完整域名
            if (count.ContainsKey(fullDomain)) {
                count[fullDomain] += visits;
            } else {
                count[fullDomain] = visits;
            }
            
            // 添加所有子域名
            for (int i = 0; i < fullDomain.Length; i++) {
                if (fullDomain[i] == '.') {
                    string subdomain = fullDomain.Substring(i + 1);
                    if (count.ContainsKey(subdomain)) {
                        count[subdomain] += visits;
                    } else {
                        count[subdomain] = visits;
                    }
                }
            }
        }
        
        var result = new List<string>();
        foreach (var pair in count) {
            result.Add($"{pair.Value} {pair.Key}");
        }
        
        return result;
    }
}

var subdomainVisits = function(cpdomains) {
    const domainCount = new Map();
    
    for (const cpdomain of cpdomains) {
        const [count, domain] = cpdomain.split(' ');
        const visitCount = parseInt(count);
        
        const parts = domain.split('.');
        
        for (let i = 0; i < parts.length; i++) {
            const subdomain = parts.slice(i).join('.');
            domainCount.set(subdomain, (domainCount.get(subdomain) || 0) + visitCount);
        }
    }
    
    const result = [];
    for (const [domain, count] of domainCount) {
        result.push(`${count} ${domain}`);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(N × M)，其中 N 是 cpdomains 的长度，M 是每个域名的平均长度
空间复杂度O(K)，其中 K 是所有不同子域名的数量