2085. 统计出现过一次的公共字符串

🟢   🔖  数组 哈希表 字符串 计数  🔗 力扣 LeetCode

题目

Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.

Example 1:

Input: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]

Output: 2

Explanation:

• "leetcode" appears exactly once in each of the two arrays. We count this string.
• "amazing" appears exactly once in each of the two arrays. We count this string.
• "is" appears in each of the two arrays, but there are 2 occurrences of it in words1. We do not count this string.
• "as" appears once in words1, but does not appear in words2. We do not count this string.

Thus, there are 2 strings that appear exactly once in each of the two arrays.

Example 2:

Input: words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]

Output: 0

Explanation: There are no strings that appear in each of the two arrays.

Example 3:

Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]

Output: 1

Explanation: The only string that appears exactly once in each of the two arrays is "ab".

Constraints:

• 1 <= words1.length, words2.length <= 1000
• 1 <= words1[i].length, words2[j].length <= 30
• words1[i] and words2[j] consists only of lowercase English letters.

题目大意

给你两个字符串数组 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. 初始化两个 Map 类型的变量 freq1 和 freq2。
2. 遍历 words1 数组，将每个单词的出现次数存储到 freq1 中。
3. 遍历 words2 数组，将每个单词的出现次数存储到 freq2 中。
4. 遍历 freq1 的所有键：
   • 判断当前单词在 freq1 中的频率是否为 1。
   • 同时判断它在 freq2 中的频率是否为 1。
   • 如果满足上述条件，则增加计数。
5. 返回计数结果。

复杂度分析

• 时间复杂度：O(n1 + n2 + k1)

  • 遍历 words1 和 words2 频率统计：O(n1 + n2)，其中 n1 和 n2 分别是两个数组的长度。
  • 遍历 freq1 的键筛选单词：O(k1)，其中 k1 是 freq1 的键数。

• 空间复杂度：O(k1 + k2)，，其中 k1 和 k2 分别是 words1 和 words2 的单词种类数，两个 Map 存储 words1 和 words2 的单词频率。

代码

/**
 * @param {string[]} words1
 * @param {string[]} words2
 * @return {number}
 */
var countWords = function (words1, words2) {
	let freq1 = new Map();
	let freq2 = new Map();

	// 统计 words1 和 words2 的频率
	for (let word of words1) {
		freq1.set(word, (freq1.get(word) || 0) + 1);
	}
	for (let word of words2) {
		freq2.set(word, (freq2.get(word) || 0) + 1);
	}

	// 遍历 words1，统计符合条件的单词
	return [...freq1.keys()].filter(
		(word) => freq1.get(word) === 1 && freq2.get(word) === 1
	).length;
};

相关题目

题号	标题	题解	标签	难度	力扣
349	两个数组的交集	[✓]	数组 哈希表 双指针 2+	🟢	🀄️ 🔗
884	两句话中的不常见单词	[✓]	哈希表 字符串 计数	🟢	🀄️ 🔗
2053	数组中第 K 个独一无二的字符串	[✓]	数组 哈希表 字符串 1+	🟢	🀄️ 🔗