【每日一题】统计出现过一次的公共字符串

Tag

【哈希表】【字符串】【2024-01-12】

---

题目来源

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

---

解题思路

方法一：哈希表

思路

使用两个哈希表分别统计 word1 和 word2 中字符串出现的次数。

遍历其中一个哈希表，如果当前遍历的字符串仅出现一次，则在另一个哈希表中查找该字符串是否也仅出现一次，如是则两个字符串数组中 都恰好出现一次 的字符串的数目加一。

算法

class Solution {
public:
    int countWords(vector<string>& words1, vector<string>& words2) {
        unordered_map<string, int> freq1, freq2;
        for (const string& word1 : words1) {
            ++freq1[word1];
        } 
        for (const string& word2 : words2) {
            ++freq2[word2];
        } 

        int res = 0;
        for (const auto& [word1, cnt1] : freq1) {
            if (cnt1 == 1 && freq2[word1] == 1) {
                ++res;
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度：$O(n+m)$，$n$ 和 $m$ 为字符串 words1 和 words2 中的长度。

空间复杂度：$O(n+m)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。