884. Uncommon Words from Two Sentences

Description

The problem is to find all uncommon words from two sentences. An uncommon word is defined as a word that appears exactly once in either sentence. Both sentences are provided as strings, and we need to return a list of all uncommon words.

Intuition

To solve this problem, we can think of counting the frequency of every word in both sentences. Any word that appears exactly once across both sentences is considered uncommon and should be added to the result.

Approach

1. Combine both sentences: First, split both sentences into words. Then, merge these two lists of words.
2. Count word occurrences: Use a dictionary (or hash map) to store the frequency of each word.
3. Filter uncommon words: Iterate through the dictionary and collect words that appear only once.
4. Return the result: Return the list of words that have a frequency of one.

Complexity

Time Complexity:

O(n), where n is the total number of words in both sentences. Splitting the sentences into words, counting word occurrences, and filtering the results all take linear time.

Space Complexity:

O(n), where n is the total number of words. We need additional space to store the frequency of words and the resulting list of uncommon words.

Code

C++

class Solution {
public:
    vector uncommonFromSentences(string s1, string s2) {
        unordered_map wordCount;
        istringstream iss1(s1), iss2(s2);
        string word;

        // Count words from s1
        while (iss1 >> word) {
            wordCount[word]++;
        }

        // Count words from s2
        while (iss2 >> word) {
            wordCount[word]++;
        }

        vector result;
        // Add words that appear only once to the result
        for (auto& entry : wordCount) {
            if (entry.second == 1) {
                result.push_back(entry.first);
            }
        }
        return result;
    }
};

Python

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        word_count = {}
        words = (s1 + " " + s2).split()

        # Count words
        for word in words:
            word_count[word] = word_count.get(word, 0) + 1

        # Collect words that appear only once
        return [word for word, count in word_count.items() if count == 1]

Java

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        Map wordCount = new HashMap<>();
        String[] words = (s1 + " " + s2).split(" ");

        // Count words
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        // Collect words that appear only once
        List result = new ArrayList<>();
        for (Map.Entry entry : wordCount.entrySet()) {
            if (entry.getValue() == 1) {
                result.add(entry.getKey());
            }
        }
        return result.toArray(new String[0]);
    }
}

JavaScript

var uncommonFromSentences = function (s1, s2) {

    const arr = [...s1.split(" "), ...s2.split(" ")];
    const map = new Map();
    
    for (let i = 0; i < arr.length; i++) {
        if (!map[arr[i]]) map[arr[i]] = 1;
        else map[arr[i]]++;
    }
    let res = [];
    for (const key of Object.keys(map)) {
        if (map[key] === 1) res.push(key);
    }
    return res;
};