884. Uncommon Words from Two Sentences

1. Description

A sentence is a string of single-space separated words where each word consists only of lowercase letters.
A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.
Given two sentences s1 and s2, return a list of all the uncommon words. You may return the answer in any order.

2. Example

Example 1

Input: s1 = “this apple is sweet”, s2 = “this apple is sour”
Output: [“sweet”,“sour”]

Example 2

Input: s1 = “apple apple”, s2 = “banana”
Output: [“banana”]

3. Constraints

• 1 <= s1.length, s2.length <= 200
• s1 and s2 consist of lowercase English letters and spaces.
• s1 and s2 do not have leading or trailing spaces.
• All the words in s1 and s2 are separated by a single space.

4. Solutions

Hash Table

n = s1.size() + s2.size()
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<string> uncommonFromSentences(const string &s1, const string &s2) {
        unordered_map<string, int> string_count;
        stringstream stream(s1 + " " + s2);
        for (string word; stream >> word;) {
            ++string_count[word];
        }

        vector<string> result;
        for (auto &word : string_count) {
            if (word.second == 1) {
                result.push_back(move(word.first));
            }
        }

        return result;
    }
};