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

题目

网站域名 “ d i s c u s s . l e e t c o d e . c o m discuss.leetcode.com discuss.leetcode.com” 由多个子域名组成。顶级域名为 “ c o m com com” ，二级域名为 “ l e e t c o d e . c o m leetcode.com leetcode.com” ，最低一级为 “ d i s c u s s . l e e t c o d e . c o m discuss.leetcode.com discuss.leetcode.com” 。当访问域名 “ d i s c u s s . l e e t c o d e . c o m discuss.leetcode.com discuss.leetcode.com” 时，同时也会隐式访问其父域名 “ l e e t c o d e . c o m leetcode.com leetcode.com” 以及 “ c o m com com” 。

计数配对域名 是遵循 “ r e p rep rep d 1. d 2. d 3 d1.d2.d3 d1.d2.d3” 或 “ r e p rep rep d 1. d 2 d1.d2 d1.d2” 格式的一个域名表示，其中 r e p rep rep 表示访问域名的次数， d 1. d 2. d 3 d1.d2.d3 d1.d2.d3 为域名本身。

例如，“ 9001 9001 9001 d i s c u s s . l e e t c o d e . c o m discuss.leetcode.com discuss.leetcode.com” 就是一个 计数配对域名 ，表示 d i s c u s s . l e e t c o d e . c o m discuss.leetcode.com discuss.leetcode.com 被访问了 9001 9001 9001 次。

给你一个 计数配对域名 组成的数组 c p d o m a i n s cpdomains 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 < = c p d o m a i n . l e n g t h < = 100 1 <= cpdomain.length <= 100 1<=cpdomain.length<=100
1 < = c p d o m a i n [ i ] . l e n g t h < = 100 1 <= cpdomain[i].length <= 100 1<=cpdomain[i].length<=100
c p d o m a i n [ i ] cpdomain[i] cpdomain[i] 会遵循 “ r e p i rep_i repi d 1 i . d 2 i . d 3 i d1_i.d2_i.d3_i d1i.d2i.d3i” 或 “ r e p i rep_i repi d 1 i . d 2 i d1_i.d2_i d1i.d2i” 格式
r e p i rep_i repi 是范围 [ 1 , 1 0 4 ] [1, 10^4] [1,104] 内的一个整数
d 1 i d1_i d1i、 d 2 i d2_i d2i 和 d 3 i d3_i d3i 由小写英文字母组成

题解

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

递归函数：统计域名访问次数。

边界条件：当前域名没有上级域名，递归结束。

如题目给出的例子，“ 9001 9001 9001 d i s c u s s . l e e t c o d e . c o m discuss.leetcode.com discuss.leetcode.com”:

先统计 d i s c u s s . l e e t c o d e . c o m discuss.leetcode.com discuss.leetcode.com 被访问了 9001 9001 9001 次。
再统计 l e e t c o d e . c o m leetcode.com leetcode.com 被访问了 9001 9001 9001 次。
再统计 c o m com com 被访问了 9001 9001 9001 次。
因为 c o m com com 已经是最顶级域名了，返回。

其中计数可以使用 哈希表 这个数据结构，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)
}

复杂度分析

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

空间复杂度: O ( K ) O(K) O(K)，K 为所有参与计数的域名个数，小于等于NM。

i余数