先上今天拍的月亮，中秋快樂~~~

題目

884. Uncommon Words from Two Sentences
難度: 用c++的話簡單

題意

給定兩字串s1及s2。字串可被空白字元切成單字。
求一字串陣列，包含所有不平常單字。
不平常單字為在其中一個字串出現一次，另一個字串沒有出現的單字。

思路

查詢有無出現、查詢出現幾次的題目類型，都優先用哈希表解。
先用兩個哈希表分別記錄兩個字串中，個別單字的出現次數；再遍歷兩哈希表的單字，檢查此單字在另一個哈希表出現的次數。

實作

可以使用istringstream將字串轉換成字串流，可以很方便的分割空白字元。
我邊查語法邊寫的，用C大概會刻到吐。

typedef std::__cxx11::basic_istringstream std::istringstream
Class for @c char input memory streams.

class Solution
{
public:
    vector<string> uncommonFromSentences(string s1, string s2)
    {
        istringstream iss1(s1);
        istringstream iss2(s2);
        // Hash map for s1, string -> count
        unordered_map<string, int> um1;
        // Hash map for s2, string -> count
        unordered_map<string, int> um2;

        // Split string in sentence and count number
        string str;
        while (iss1 >> str)
            um1[str]++;
        while (iss2 >> str)
            um2[str]++;

        // Find uncommon words
        vector<string> res;
        for (auto word : um1)
            if (word.second == 1 && um2.find(word.first) == um2.end())
                res.push_back(word.first);
        for (auto word : um2)
            if (word.second == 1 && um1.find(word.first) == um1.end())
                res.push_back(word.first);

        return res;
    }
};

分析

若s1長度為N1，s2長度為N2
時間複雜度: O(N1 + N2) = O(max(N1, N2))，每個單字建表、查表都最多各一次。
空間複雜度: O(N1 + N2)，哈希表所需的空間。

結果

Accepted
55/55 cases passed (5 ms)
Your runtime beats 15.91 % of cpp submissions
Your memory usage beats 22.25 % of cpp submissions (9.2 MB)