#884

Easy

LeetCode Problem Workspace

Uncommon Words from Two Sentences

Find uncommon words from two sentences by counting word frequencies using hash tables.

Problem Statement

You are given two sentences, s1 and s2, where each sentence is a string of single-space separated words containing only lowercase letters. A word is considered uncommon if it appears exactly once in one sentence and does not appear in the other sentence.

Your task is to return a list of all uncommon words. The words should be returned in any order. This problem can be efficiently solved using hash tables and string operations.

Examples

Example 1

Input: s1 = "this apple is sweet", s2 = "this apple is sour"

Output: ["sweet","sour"]

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"]

Example details omitted.

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.

Solution Approach

Count Word Frequencies

First, count the frequency of each word in both sentences using hash tables. This allows us to track which words are uncommon.

Filter Uncommon Words

Once we have the word frequencies, filter out the words that appear more than once in either sentence. The remaining words are those that are unique to one sentence.

Return Result

Finally, collect all the words that appear exactly once in one sentence and not in the other sentence, and return them in a list.

Complexity Analysis

Metric	Value
Time	O(M + N)
Space	O(M + N)

The time complexity is O(M + N), where M and N are the lengths of the two sentences. We iterate over both sentences to count the word frequencies, and this process is linear. The space complexity is also O(M + N) due to the space required to store the word frequencies in hash tables.

What Interviewers Usually Probe

The candidate demonstrates understanding of hash tables for counting word frequencies.
The candidate should be able to implement the filtering of uncommon words efficiently.
The candidate should be aware of handling edge cases, like repeated words within a sentence.

Common Pitfalls or Variants

Common pitfalls

Not correctly handling words that appear more than once in either sentence.
Failing to account for cases where no uncommon words exist.
Incorrectly counting words, missing one of the sentences, or not using hash tables properly for counting.

Follow-up variants

Modify the problem to return words that appear exactly twice in each sentence.
Handle cases where multiple uncommon words exist but with a higher frequency.
Optimize the solution for larger datasets by considering more advanced data structures.

FAQ

What is the best approach to solve 'Uncommon Words from Two Sentences'?

The most efficient way to solve this problem is by using hash tables to count the frequency of each word in both sentences and then filtering out the uncommon ones.

How do I filter uncommon words from two sentences?

After counting the word frequencies, filter the words that appear exactly once in one sentence and not in the other.

What data structures can I use to solve the problem?

Hash tables are ideal for this problem as they allow efficient counting and filtering of words.

What is the time complexity of this problem?

The time complexity is O(M + N), where M and N are the lengths of the two sentences.

Can I optimize the solution for large inputs?

Yes, you can optimize the solution by considering more advanced data structures or parallelizing the word counting process.

terminal

Solution

Solution 1: Hash Table

According to the problem description, as long as a word appears once, it meets the requirements of the problem. Therefore, we use a hash table `cnt` to record all words and their occurrence counts.

1

2

3

4

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        cnt = Counter(s1.split()) + Counter(s2.split())
        return [s for s, v in cnt.items() if v == 1]

Continue Practicing

#819 most common word #811 subdomain visit count #767 reorganize string