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

待我称王封你为后i 2024-03-16 17:25 58阅读 0赞

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

### 题目 ###

网站域名 “ 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”:

1.  先统计  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 次。
2.  再统计  l e e t c o d e . c o m leetcode.com leetcode.com 被访问了  9001 9001 9001 次。
3.  再统计  c o m com com 被访问了  9001 9001 9001 次。
4.  因为  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`。