#884
Uncommon Words from Two Sentences
EasyHash TableStringCountingHash MapArray
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
The optimal approach uses a hash map to count the occurrences of each word in both sentences. This allows us to efficiently determine which words are uncommon by checking their counts in a single pass.
⚙️
Algorithm
3 steps- 1Step 1: Split both sentences into lists of words.
- 2Step 2: Create a hash map to count occurrences of each word from both lists.
- 3Step 3: Iterate through the hash map and collect words that appear exactly once.
solution.py5 lines
1def uncommonFromSentences(s1, s2):
2 from collections import Counter
3 words = s1.split() + s2.split()
4 count = Counter(words)
5 return [word for word in count if count[word] == 1 and (word in s1.split() or word in s2.split())]ℹ
Complexity note: The time complexity is O(n) because we only pass through the list of words a constant number of times (once to count and once to filter). The space complexity is O(n) due to the storage of word counts in the hash map.
- 1Uncommon words must appear exactly once in one sentence and not at all in the other.
- 2Using a hash map allows for efficient counting and retrieval.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.