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.
Example 1:
Input: s1 = "this apple is sweet", s2 = "this apple is sour"
Output: ["sweet","sour"]
Explanation:
The word "sweet" appears only in s1, while the word "sour" appears only in s2.
Example 2:
Input: s1 = "apple apple", s2 = "banana"
Output: ["banana"]
Constraints:
1 <= s1.length, s2.length <= 200s1 and s2 consist of lowercase English letters and spaces.s1 and s2 do not have leading or trailing spaces.s1 and s2 are separated by a single space.In this approach, we compute the frequency of each word in both sentences. We then check for words that appear exactly once in one sentence and do not appear in the other sentence. This can be efficiently achieved by using hash maps (or dictionaries) to store these frequencies.
First, we split each of the sentences into words and count the occurrences using the Counter class from the collections module. We then iterate over these counts and check for words that meet our uncommon criteria. These words are collected in a result list.
JavaScript
Time Complexity: O(n + m), where n and m are the lengths of s1 and s2 respectively, due to splitting and counting.
Space Complexity: O(n + m) due to storage for hash maps.
This approach involves merging both sentences into one list of words, along with a source identifier to track which sentence they came from. By counting occurrences in this merged list, we can determine uncommon words.
We merge the two sentences into one using a stream to count each word's occurrence, identifying those that appear only once. Since these unique words have a count of 1, they are the uncommon words across both sentences.
Java
Time Complexity: O(n + m) merging and counting stages.
Space Complexity: O(n + m) for the storage of counts.
| Approach | Complexity |
|---|---|
| Using Frequency Count | Time Complexity: O(n + m), where n and m are the lengths of s1 and s2 respectively, due to splitting and counting. Space Complexity: O(n + m) due to storage for hash maps. |
| Merging and Identifying Uniques | Time Complexity: O(n + m) merging and counting stages. Space Complexity: O(n + m) for the storage of counts. |
Uncommon Words from Two Sentences - Leetcode 884 - Python • NeetCodeIO • 5,786 views views
Watch 9 more video solutions →Practice Uncommon Words from Two Sentences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor