【算法题解】39. 子域名访问计数的递归解法

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/subdomain-visit-count/

❞

题目

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

「计数配对域名」 是遵循 “ ” 或 “ ” 格式的一个域名表示，其中表示访问域名的次数，为域名本身。

例如，” ” 就是一个 「计数配对域名」 ，表示被访问了次。

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

示例 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 次。

提示：

会遵循 “ ” 或 “ ” 格式
是范围内的一个整数
、和由小写英文字母组成

题解

先统计累计当前域名的访问次数，如果当前域名存在上级域名，则继续向上统计上级域名的访问次数。

递归函数：统计域名访问次数。
边界条件：当前域名没有上级域名，递归结束。

如题目给出的例子，” “:

先统计被访问了次。
再统计被访问了次。
再统计被访问了次。
因为已经是最顶级域名了，返回。

其中计数可以使用 「哈希表」 这个数据结构，key为域名，value为出现的次数。

Java 代码实现


class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        List<String> results = new ArrayList<>();
        Map<String, Integer> accessMap = new HashMap<>();


        for(int i = 0; i < cpdomains.length; i++){
            String[] cpdomainArray = cpdomains[i].split(" ");
            int count = Integer.valueOf(cpdomainArray[0]);
            String domain = cpdomainArray[1];
            this.countDomain(domain, accessMap, count);
           
        }

        if(!accessMap.isEmpty()){
            StringBuilder sb = new StringBuilder();
            for(String domain: accessMap.keySet()){
                results.add(sb.append(accessMap.get(domain)).append(" ").append(domain).toString());
                sb.delete(0, sb.length());
            }
        }
        return results;
    }

    private void countDomain(String domain, Map<String, Integer> accessMap, int count){

        accessMap.put(domain, accessMap.getOrDefault(domain, 0) + count);

        int index = domain.indexOf(".");
        if(index == -1){
            return;
        }
        
        // 统计上级域名
        this.countDomain(domain.substring(index + 1), accessMap, count);
        
    }
}

Go 代码实现


func subdomainVisits(cpdomains []string) []string {
    accessMap := map[string]int{}
    for _, cpdomain := range cpdomains {
        
        splits := strings.Split(cpdomain, " ")
  countStr := splits[0]
  count, _ := strconv.Atoi(countStr)

        domain := splits[1]
        countDomain(domain, count, accessMap)

    }

    ans := make([]string, 0, len(accessMap))
    for domain, count := range accessMap {
        ans = append(ans, strconv.Itoa(count) + " " + domain)
    }
    return ans
}

func countDomain(domain string, count int, accessMap map[string]int) {
    accessMap[domain] += count

    index := strings.IndexByte(domain, '.')
    if index == -1 {
        return
    }

    countDomain(domain[index + 1 :], count, accessMap)
}

复杂度分析

时间复杂度: ，N 为给定数组 cpdomains 的大小；M 为给定的这些域名可以分解出的域名个数的最大值，如域名 "discuss.leetcode.com" 可以分解出 3 个域名用于计数。
空间复杂度: ，K 为所有参与计数的域名个数，小于等于NM。