LC 811. 子域名访问计数

题目描述

这是 LeetCode 上的 811. 子域名访问计数 ，难度为 中等。

网站域名 "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] 会遵循 "repi d1i.d2i.d3i" 或 "repi d1i.d2i" 格式
• repi 是范围 $[1, 10^4]$ 内的一个整数
• $d1_i$、$d2_i$ 和 $d3_i$ 由小写英文字母组成

---

哈希表

为了方便，我们令 cpdomains 为 ss。

根据题意进行模拟：使用哈希表记录每个域名的总访问次数，从前往后处理所有的 $ss[i]$。在处理某个 $ss[i]$ 时（记长度为 $n$，使用指针 idx 代指扫描到的游标位置），先通过指针扫描找到访问数字部分 cnt = ss[i][0:idx]，然后「从后往前」处理 $ss[i]$ 的 $[idx + 1, n - 1]$ 部分，按照域名层级「从小到大」的顺序进行截取，并累加访问次数 cnt 到当前域名。

最后根据哈希表构造答案。

Java 代码：

class Solution {
    public List<String> subdomainVisits(String[] ss) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : ss) {
            int n = s.length(), idx = 0;
            while (idx < n && s.charAt(idx) != ' ') idx++;
            int cnt = Integer.parseInt(s.substring(0, idx));
            int start = idx + 1; idx = n - 1;
            while (idx >= start) {
                while (idx >= start && s.charAt(idx) != '.') idx--;
                String cur = s.substring(idx + 1);
                map.put(cur, map.getOrDefault(cur, 0) + cnt);
                idx--;
            }
        }
        List<String> ans = new ArrayList<>();
        for (String key : map.keySet()) ans.add(map.get(key) + " " + key);
        return ans;
    }
}

TypeScript 代码：

function subdomainVisits(ss: string[]): string[] {
    const map = new Map<string, number>()
    for (const s of ss) {
        let n = s.length, idx = 0
        while (idx < n && s[idx] != ' ') idx++
        const cnt = Number(s.substring(0, idx))
        const start = idx + 1; idx = n - 1
        while (idx >= start) {
            while (idx >= start && s[idx] != '.') idx--
            const cur = s.substring(idx + 1)
            if (!map.has(cur)) map.set(cur, 0)
            map.set(cur, map.get(cur) + cnt)
            idx--
        }
    }
    const ans = new Array<string>()
    for (const key of map.keys()) ans.push(map.get(key) + " " + key)
    return ans
};

Python 代码：

class Solution:
    def subdomainVisits(self, ss: List[str]) -> List[str]:
        mapping = defaultdict(int)
        for s in ss:
            n, idx = len(s), 0
            while idx < n and s[idx] != ' ':
                idx += 1
            cnt = int(s[:idx])
            start, idx = idx + 1, n - 1
            while idx >= start:
                while idx >= start and s[idx] != '.':
                    idx -= 1
                mapping[s[idx + 1:]] += cnt
                idx -= 1
        return [f'{v} {k}' for k, v in mapping.items()]

• 时间复杂度：$O(\sum_{i = 0}^{n - 1}len(ss[i]))$
• 空间复杂度：$O(\sum_{i = 0}^{n - 1}len(ss[i]))$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.811 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。