Easy

题目描述

给定两个字符串数组 words1 和 words2，返回在两个数组中都恰好出现一次的字符串的数目。

示例 1:

输入：words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
输出：2
解释：
- "leetcode" 在两个数组中都恰好出现一次，我们计数这个字符串。
- "amazing" 在两个数组中都恰好出现一次，我们计数这个字符串。
- "is" 在两个数组中都出现，但在 words1 中出现了 2 次。我们不计数这个字符串。
- "as" 在 words1 中出现一次，但在 words2 中没有出现。我们不计数这个字符串。
因此，在两个数组中都恰好出现一次的字符串有 2 个。

示例 2:

输入：words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
输出：0
解释：没有字符串在两个数组中都出现。

示例 3:

输入：words1 = ["a","ab"], words2 = ["a","a","a","ab"]
输出：1
解释：唯一在两个数组中都恰好出现一次的字符串是 "ab"。

约束条件:

  • 1 <= words1.length, words2.length <= 1000
  • 1 <= words1[i].length, words2[j].length <= 30
  • words1[i] 和 words2[j] 只包含小写英文字母

提示:

  • 能否尝试遍历每个单词？
  • 能否使用哈希表来达到良好的复杂度？

解题思路

解题思路

这个问题的核心是找到在两个数组中都恰好出现一次的字符串。我们需要分别统计每个数组中每个字符串的出现次数，然后找出在两个数组中出现次数都为1的字符串。

解法一：两次遍历 + 哈希表（推荐）

  1. 分别统计两个数组中每个字符串的出现次数，使用两个哈希表存储
  2. 遍历其中一个哈希表，检查每个字符串是否在两个数组中都恰好出现一次
  3. 满足条件的字符串计数加一

解法二：一次遍历优化

先统计第一个数组的字符串频次，然后遍历第二个数组，同时更新计数并判断。

解法三：集合操作

分别找出两个数组中只出现一次的字符串，然后求交集。

推荐使用解法一，因为思路最清晰，代码可读性强，且时间复杂度已经是最优的O(n+m)。

代码实现

class Solution {
public:
    int countWords(vector<string>& words1, vector<string>& words2) {
        unordered_map<string, int> count1, count2;
        
        // 统计两个数组中字符串的出现次数
        for (const string& word : words1) {
            count1[word]++;
        }
        for (const string& word : words2) {
            count2[word]++;
        }
        
        int result = 0;
        // 检查在两个数组中都恰好出现一次的字符串
        for (const auto& pair : count1) {
            if (pair.second == 1 && count2[pair.first] == 1) {
                result++;
            }
        }
        
        return result;
    }
};

class Solution:
    def countWords(self, words1: List[str], words2: List[str]) -> int:
        from collections import Counter
        
        # 统计两个数组中字符串的出现次数
        count1 = Counter(words1)
        count2 = Counter(words2)
        
        result = 0
        # 检查在两个数组中都恰好出现一次的字符串
        for word in count1:
            if count1[word] == 1 and count2[word] == 1:
                result += 1
                
        return result

public class Solution {
    public int CountWords(string[] words1, string[] words2) {
        var count1 = new Dictionary<string, int>();
        var count2 = new Dictionary<string, int>();
        
        // 统计两个数组中字符串的出现次数
        foreach (string word in words1) {
            count1[word] = count1.GetValueOrDefault(word, 0) + 1;
        }
        foreach (string word in words2) {
            count2[word] = count2.GetValueOrDefault(word, 0) + 1;
        }
        
        int result = 0;
        // 检查在两个数组中都恰好出现一次的字符串
        foreach (var pair in count1) {
            if (pair.Value == 1 && count2.GetValueOrDefault(pair.Key, 0) == 1) {
                result++;
            }
        }
        
        return result;
    }
}

var countWords = function(words1, words2) {
    const count1 = {};
    const count2 = {};
    
    for (const word of words1) {
        count1[word] = (count1[word] || 0) + 1;
    }
    
    for (const word of words2) {
        count2[word] = (count2[word] || 0) + 1;
    }
    
    let result = 0;
    for (const word in count1) {
        if (count1[word] === 1 && count2[word] === 1) {
            result++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n + m)n 是 words1 的长度，m 是 words2 的长度，需要遍历两个数组进行统计
空间复杂度O(n + m)需要两个哈希表分别存储两个数组中不同字符串的计数

相关题目