Difficulty: Easy | Acceptance: 75.70% | Paid: No Topics: Hash Table, String, Counting
A sentence is a string of single-space separated words. Each word consists only of lowercase letters.
A sentence can be empty or contain leading/trailing spaces. However, your result should not contain leading/trailing spaces.
You need to return all uncommon words.
A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.
- Examples
- Constraints
- Approach 1: Hash Map Counting
- Approach 2: Sorting and Linear Scan
Examples
Example 1:
Input: s1 = "this apple is sweet", s2 = "this apple is sour"
Output: ["sweet","sour"]
Explanation:
The word "this" appears in both sentences.
The word "apple" appears in both sentences.
The word "sweet" appears only in s1.
The word "sour" appears only in s2.
Example 2:
Input: s1 = "apple apple", s2 = "banana"
Output: ["banana"]
Explanation:
The word "apple" appears twice in s1.
The word "banana" appears once in s2.
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.
Approach 1: Hash Map Counting
Intuition We can count the frequency of every word across both sentences. A word is “uncommon” if and only if its total frequency is exactly 1.
Steps
- Split both input strings into arrays of words.
- Use a hash map to count the occurrences of each word from the first sentence.
- Update the hash map with counts from the second sentence.
- Iterate through the map and collect all words that have a count of exactly 1.
from typing import List
import collections
class Solution:
def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
count = collections.Counter(s1.split())
count.update(s2.split())
return [word for word, freq in count.items() if freq == 1]
Complexity
- Time: O(N + M), where N and M are the lengths of the two sentences.
- Space: O(N + M) to store the words and the frequency map.
- Notes: This is the most optimal approach for time complexity.
Approach 2: Sorting and Linear Scan
Intuition If we concatenate the words from both sentences and sort them, duplicate words will be adjacent. We can then scan the sorted list to find words that are not equal to their neighbors.
Steps
- Split both sentences into arrays and combine them.
- Sort the combined array of words.
- Iterate through the sorted array. A word is uncommon if it is different from the previous word and different from the next word.
- Handle edge cases for the first and last elements in the array.
from typing import List
class Solution:
def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
words = s1.split() + s2.split()
words.sort()
res = []
n = len(words)
for i in range(n):
prev = words[i-1] if i > 0 else None
next = words[i+1] if i < n - 1 else None
if words[i] != prev and words[i] != next:
res.append(words[i])
return res
Complexity
- Time: O((N + M) log (N + M)) due to the sorting step.
- Space: O(N + M) to store the list of words.
- Notes: This approach is slower than the hash map approach due to sorting, but uses a different algorithmic paradigm.