题目描述

给定两个句子 A 和 B。（ 句子 是一串由空格分隔的单词。每个单词仅由小写字母组成。）

如果一个单词在其中一个句子中只出现一次，在另一个句子中却没有出现，那么这个单词就是 不常见的 。

返回所有不常用单词的列表。

您可以按任何顺序返回列表。

样例

输入：A = "this apple is sweet", B = "this apple is sour"
输出：["sweet","sour"]

输入：A = "apple apple", B = "banana"
输出：["banana"]

注意

• 0 <= A.length <= 200
• 0 <= B.length <= 200
• A 和 B 都只包含空格和小写字母。

算法

(枚举) $O(n + m)$

1. 将 A 字符串和 B 字符串按空格分解为单词存放在各自的数组中。
2. 开两个 unordered_map 来记录每个字符串中每个单词出现的次数。
3. 依次枚举每个单词，判断是否为答案即可。

时间复杂度

• 每个字母都只需要遍历常数次，unordered_map 的插入和查询时间复杂度为常数，故总时间复杂度为 $O(n + m)$。

空间复杂度

• 需要额外的数组和哈希表，故空间复杂度为 $O(n + m)$。

C++ 代码

class Solution {
public:

    void split(const string &s, vector<string> &w) {
        int n = s.length();
        int last = 0;
        for (int i = 0; i < n; i++)
            if (s[i] == ' ') {
                w.emplace_back(s.substr(last, i - last));
                last = i + 1;
            }
        w.emplace_back(s.substr(last, n - last));
    }

    vector<string> uncommonFromSentences(string A, string B) {
        unordered_map<string, int> dicA, dicB;
        vector<string> wordsA, wordsB, ans;
        split(A, wordsA);
        split(B, wordsB);

        for (auto &word : wordsA)
            dicA[word]++;

        for (auto &word: wordsB)
            dicB[word]++;

        for (auto &word : wordsA)
            if (dicA[word] == 1 && dicB.find(word) == dicB.end())
                ans.push_back(word);

        for (auto &word: wordsB)
            if (dicB[word] == 1 && dicA.find(word) == dicA.end())
                ans.push_back(word);

        return ans;
    }
};