LeetCode 题解工作台
统计出现过一次的公共字符串
给你两个字符串数组 words1 和 words2 ，请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。 示例 1： 输入： words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is…
4
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以用两个哈希表 和 分别统计两个字符串数组中每个字符串出现的次数，然后遍历其中一个哈希表，如果某个字符串在另一个哈希表中出现了一次，且在当前哈希表中也出现了一次，则答案加一。 时间复杂度 $O(n + m)$，空间复杂度 $O(n + m)$。其中 和 分别是两个字符串数组的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你两个字符串数组 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 <= 10001 <= words1[i].length, words2[j].length <= 30words1[i]和words2[j]都只包含小写英文字母。
解题思路
方法一：哈希表计数
我们可以用两个哈希表 和 分别统计两个字符串数组中每个字符串出现的次数，然后遍历其中一个哈希表，如果某个字符串在另一个哈希表中出现了一次，且在当前哈希表中也出现了一次，则答案加一。
时间复杂度 ，空间复杂度 。其中 和 分别是两个字符串数组的长度。
class Solution:
def countWords(self, words1: List[str], words2: List[str]) -> int:
cnt1 = Counter(words1)
cnt2 = Counter(words2)
return sum(v == 1 and cnt2[w] == 1 for w, v in cnt1.items())
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m) where n and m are the lengths of words1 and words2, since each array is scanned once and hash lookups are constant time. Space complexity is O(n + m) for storing frequency counts in hash maps. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you tracking frequency efficiently without nested loops?
- question_mark
Did you consider strings that appear more than once in one array?
- question_mark
Can you achieve linear time using hash tables for this problem?
常见陷阱
外企场景- error
Counting strings that appear multiple times in one array.
- error
Using nested loops instead of hash maps, increasing time complexity.
- error
Forgetting to check both arrays for exactly one occurrence.
进阶变体
外企场景- arrow_right_alt
Count strings appearing at least once in both arrays instead of exactly once.
- arrow_right_alt
Count strings appearing exactly k times in both arrays.
- arrow_right_alt
Return the list of strings that satisfy the one-occurrence condition instead of just the count.