811. 子域名访问计数
题目描述
域名由若干部分用点号连接而成，例如 discuss.leetcode.com。它的父域名依次是去掉最左边一段后得到的 leetcode.com 和 com。访问某个域名时，它的每个父域名也都算被访问了同样多次。
输入字符串数组 cpdomains，每一项形如 "rep d1.d2.d3" 或 "rep d1.d2"：前面是访问次数 rep，空格后面是域名。
汇总后，对出现过的每一个域名（包括所有父域名）统计总访问次数，按 "次数 域名" 的格式组成字符串数组返回，元素顺序不限。
示例 1
输入：cpdomains = ["9001 discuss.leetcode.com"] 输出：["9001 discuss.leetcode.com","9001 leetcode.com","9001 com"]
解释：访问 discuss.leetcode.com 9001 次，同时 leetcode.com 和 com 也各被访问 9001 次。
示例 2
输入：cpdomains = ["900 google.mail.com","50 yahoo.com","1 intel.mail.com","5 wiki.org"] 输出：["900 google.mail.com","901 mail.com","951 com","50 yahoo.com","1 intel.mail.com","5 wiki.org","5 org"]
解释：mail.com 累计 900+1=901 次，com 累计 900+50+1=951 次，org 为 5 次。
数据范围
1 <= cpdomain.length <= 1001 <= cpdomain[i].length <= 100cpdomain[i]的格式为"rep_i d1_i.d2_i.d3_i"或"rep_i d1_i.d2_i"。rep_i是[1, 10^4]范围内的整数。d1_i、d2_i、d3_i只含小写英文字母。
解题思路
用哈希表记录每个子域名的次数。对每一项，先拆出次数和域名，再把域名按点切成若干段。从第 i 段到末尾重新用点连接，就得到一个子域名，给它加上次数。最后把哈希表里每一项转成 "次数 域名" 的字符串。
为什么正确
处理完前 j 项后，cnt[d] 等于前 j 项中以 d 为子域名（即末尾若干段）的域名的访问次数之和。
复杂度分析
设所有字符串总长为 L，每个域名最多 3 段，时间 O(L)，空间 O(L)。
易错点
次数要先转成整数再累加，否则会变成字符串拼接；Java 的 split(".") 是正则，要写成 split("\\.")。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
cnt = {}
for cp in cpdomains:
num, dom = cp.split()
parts = dom.split('.')
for i in range(len(parts)):
sub = '.'.join(parts[i:])
cnt[sub] = cnt.get(sub, 0) + int(num)
return [str(c) + ' ' + d for d, c in cnt.items()]class Solution {
public List<String> subdomainVisits(String[] cpdomains) {
Map<String, Integer> cnt = new HashMap<>();
for (String cp : cpdomains) {
String[] nd = cp.split(" ");
int num = Integer.parseInt(nd[0]);
String[] parts = nd[1].split("\\.");
for (int i = 0; i < parts.length; i++) {
String sub = String.join(".", Arrays.copyOfRange(parts, i, parts.length));
cnt.put(sub, cnt.getOrDefault(sub, 0) + num);
}
}
List<String> res = new ArrayList<>();
for (Map.Entry<String, Integer> e : cnt.entrySet()) res.add(e.getValue() + " " + e.getKey());
return res;
}
}class Solution {
public:
vector<string> subdomainVisits(vector<string>& cpdomains) {
unordered_map<string, int> cnt;
for (const string& cp : cpdomains) {
size_t sp = cp.find(' ');
int num = stoi(cp.substr(0, sp));
string dom = cp.substr(sp + 1);
vector<size_t> starts = {0};
for (size_t k = 0; k < dom.size(); k++) if (dom[k] == '.') starts.push_back(k + 1);
for (size_t i = 0; i < starts.size(); i++) {
string sub = dom.substr(starts[i]);
cnt[sub] += num;
}
}
vector<string> res;
for (auto& [d, c] : cnt) res.push_back(to_string(c) + " " + d);
return res;
}
};func subdomainVisits(cpdomains []string) []string {
cnt := map[string]int{}
for _, cp := range cpdomains {
nd := strings.Fields(cp)
num, _ := strconv.Atoi(nd[0])
parts := strings.Split(nd[1], ".")
for i := range parts {
sub := strings.Join(parts[i:], ".")
cnt[sub] += num
}
}
res := []string{}
for d, c := range cnt {
res = append(res, strconv.Itoa(c)+" "+d)
}
return res
}var subdomainVisits = function(cpdomains) {
const cnt = new Map();
for (const cp of cpdomains) {
const [num, dom] = cp.split(' ');
const parts = dom.split('.');
for (let i = 0; i < parts.length; i++) {
const sub = parts.slice(i).join('.');
cnt.set(sub, (cnt.get(sub) || 0) + Number(num));
}
}
return [...cnt].map(([d, c]) => c + ' ' + d);
};function subdomainVisits(cpdomains: string[]): string[] {
const cnt = new Map<string, number>();
for (const cp of cpdomains) {
const [num, dom] = cp.split(' ');
const parts = dom.split('.');
for (let i = 0; i < parts.length; i++) {
const sub = parts.slice(i).join('.');
cnt.set(sub, (cnt.get(sub) || 0) + Number(num));
}
}
return [...cnt].map(([d, c]) => c + ' ' + d);
}