Problem Description
Given two sentences s1 and s2, return a list of all the uncommon words. A word is considered uncommon if it appears exactly once in one of the sentences and does not appear in the other sentence.
Key Insights
- Use a hash table (dictionary) to count the occurrences of each word in both sentences.
- Identify words that occur exactly once in either sentence and not at all in the other.
- Return the list of these uncommon words.
Space and Time Complexity
Time Complexity: O(n + m), where n is the number of words in s1 and m is the number of words in s2.
Space Complexity: O(n + m) for storing the words and their counts in a hash table.
Solution
To solve the problem, we can employ a hash table to count occurrences of each word in both sentences. We first split both sentences into words, then populate the hash table with their counts. Finally, we iterate through the hash table to find words that are unique to each sentence (appear exactly once in one sentence and not at all in the other).