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

标签: 数组 哈希表 字符串 计数

难度: 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] 都只包含小写英文字母。

Submission

运行时间: 16 ms

内存: 17.0 MB

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())

Explain

本题的解决方案通过使用Python的collections.Counter类来创建两个字典，分别统计words1和words2中每个字符串的出现次数。然后，遍历words1的计数器（cnt1），检查每个字符串在两个数组中是否都恰好出现了一次。如果一个字符串在words1中出现一次，并且在words2中也出现一次，这个字符串就符合条件。最后，对所有符合条件的字符串计数，得到最终结果。

时间复杂度: O(n + m)

空间复杂度: O(n + m)

class Solution:
    def countWords(self, words1: List[str], words2: List[str]) -> int:
        cnt1 = Counter(words1)  # 计数words1中每个字符串的出现次数
        cnt2 = Counter(words2)  # 计数words2中每个字符串的出现次数
        # 计算在两个字典中都恰好出现一次的字符串数量
        return sum(v == 1 and cnt2[w] == 1 for w, v in cnt1.items())

Explore

使用Python的collections.Counter类可以更简洁和高效地计算字符串的出现次数。Counter类是专门为计数任务设计的，它基于字典实现，但提供了额外的功能和优化，可以自动处理元素的初始化和计数增加，避免了手动字典时可能出现的错误和冗余代码。此外，Counter还提供了其他有用的方法，如most_common()，可以方便地进行进一步的数据分析和操作。

如果words1或words2中任一数组为空，Counter对应的字典将不包含任何元素，那么在执行求和计算符合条件的字符串数量时，由于其中一个字典中不包含任何键，所以对于任何来自另一非空数组的字符串，检查其是否在空的字典中出现一次都将返回False。因此，最终结果将是0，表示没有字符串同时在两个列表中恰好出现一次。这种情况下，算法自然而然地处理了空数组的输入，不需要额外的条件判断。

为了优化大数据集时的内存使用和执行效率，可以考虑以下策略：1. 使用更高效的数据结构，如使用HashMap以减少内存开销。2. 在读取数据时采用流式处理，逐步计数而不是一次性加载整个数据集到内存中。3. 对于非常大的数据集，可以考虑使用分布式处理，例如MapReduce模式，将数据集分割成多个部分，分别在不同的机器上进行计数，然后合并结果。4. 对数据进行预处理，如去除不可能符合条件的元素，这样可以减少后续处理的数据量。5. 利用多线程或异步处理来提高处理速度。这些策略可以根据实际数据的特点和资源的可用性灵活选择。