哈希表实战：力扣2085题"统计唯一公共字符串"的优雅解法全解析

一、问题描述

给定两个字符串数组words1和words2，要求统计在两个数组中都恰好出现一次的公共字符串的数量。

示例：

输入：words1 = ["LeetCode","is","amazing","as","is"], 

          words2 = ["amazing","leetcode","is"]

输出：2

解释："leetcode"和"amazing"在两个数组中都恰好出现一次

二、解题思路

采用"哈希表统计+交集筛选"策略：

1. 分别统计两个数组中每个单词的出现频率

2. 找出两个数组中只出现一次的单词集合

3. 计算这两个集合的交集大小

三、算法详解

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespACe std;

class Solution {
public:
    int countWords(vector<string>& words1, vector<string>& words2) {
        // 统计words1中每个单词的出现次数
        unordered_map<string, int> count1;
        for (const string& word : words1) {
            count1[word]++;
        }
        
        // 统计words2中每个单词的出现次数
        unordered_map<string, int> count2;
        for (const string& word : words2) {
            count2[word]++;
        }
        
        // 收集words1中只出现一次的单词
        unordered_set<string> once1;
        for (const auto& [word, cnt] : count1) {
            if (cnt == 1) {
                once1.insert(word);
            }
        }
        
        // 收集words2中只出现一次的单词
        unordered_set<string> once2;
        for (const auto& [word, cnt] : count2) {
            if (cnt == 1) {
                once2.insert(word);
            }
        }
        
        // 计算两个集合的交集大小
        int result = 0;
        for (const string& word : once1) {
            if (once2.count(word)) {
                result++;
            }
        }
        
        return result;
    }
};

四、算法详解

1. 数据结构选择

• 使用unordered_map统计词频：O(1)时间复杂度的查找和插入

• 使用unordered_set存储唯一单词：快速查找和去重

2. 核心处理流程

1. ‌第一次遍历‌：统计words1中每个单词的出现次数

2. ‌第二次遍历‌：统计words2中每个单词的出现次数

3. ‌筛选唯一词‌：从两个统计结果中筛选出只出现一次的单词

4. ‌求交集‌：计算两个唯一词集合的交集大小

3. 优化思路

• 可以合并统计和筛选步骤，减少遍历次数

• 对于较小的输入，使用普通数组可能更高效

• 如果内存有限，可以流式处理而不存储所有单词

五、关键点解析

1. 哈希表的使用技巧

• count1[word]++自动处理不存在的键

• 使用结构化绑定[word, cnt]简化迭代

• unordered_set的count方法快速判断元素存在性

2. 边界条件处理

• 空数组输入的处理

• 所有单词都重复的情况

• 没有公共单词的情况

• 大小写敏感问题(本题假设区分大小写)

3. 复杂度分析

• 时间复杂度：O(n+m) 两次遍历加一次集合查询

• 空间复杂度：O(n+m) 需要存储两个哈希表和两个集合

六、常见错误分析

1. ‌错误统计次数‌：直接比较两个数组的单词而不统计次数

2. ‌重复计算‌：没有正确处理在两个数组中都出现多次的单词

3. ‌集合使用不当‌：错误使用vector代替set导致查找效率低下

4. ‌边界遗漏‌：没有考虑空输入或没有匹配的情况