884. Uncommon Words from Two Sentences

EasyHash TableString
Leetcode Link

Problem Description

The given problem involves finding words that are unique to each of two separate sentences. In more detail, a 'sentence' is defined as a string of words, with each word being separated by a single space and consisting only of lowercase letters. A word is deemed 'uncommon' if it satisfies two requirements: firstly, it must appear exactly once within either sentence; secondly, it must not appear in the other sentence at all.

To solve this problem, we are tasked with comparing two distinct sentences, identified as s1 and s2. The goal is to curate a list containing all such 'uncommon' words. The solution does not require the words to be in any particular sequence, implying that the words can be listed in any order. The core challenge lies in devising an efficient method to distinguish which words appear only once in either sentence and do not show up in the other.

Intuition

To arrive at the solution for identifying uncommon words from two sentences, consider a straightforward approach: counting the occurrences of each word across both sentences. By combining the counts, we can determine if a word is uncommon by checking if its total count is exactly one, signifying it appears only once and isn't shared between the two sentences.

The Python Counter class from the collections module simplifies this task. It allows us to count the frequency of elements within an iterable, such as a list of words. Therefore, the first step is to split each sentence into a list of words using the split() method, which naturally separates the sentence according to spaces. Applying Counter to these lists provides a dictionary-like object where keys are the words and values are their respective counts.

The next step is to combine these counts. The + operator merges the two Counter objects in a way that adds up the counts for common words between s1 and s2. This merged counter now holds the total frequency of every word in both sentences.

The final step is straightforward: iterate over the items in the combined counter and select the words (s) where the associated count (v) is exactly one. These words are the 'uncommon' words which need to be returned. Using list comprehension makes this step concise and efficient, resulting in a one-liner solution that fetches the required list of uncommon words.

In essence, the solution leverages the power of Python's standard library to perform the frequency analysis and then filters the results to match the specific criterion laid out in the problem statement.

Solution Approach

The solution uses the Counter data structure from Python's collections module to implement the approach efficiently. Here's how the implementation breaks down:

  1. Split the sentences into words: The first step is to split s1 and s2 into individual words based on spaces. This is done using Python's built-in split() method:

    1words_s1 = s1.split()
    2words_s2 = s2.split()

    After this step, words_s1 and words_s2 are lists that contain all the words from s1 and s2, respectively.

  2. Count the word occurrences: Next, we create two Counter objects for these lists:

    1counter_s1 = Counter(words_s1)
    2counter_s2 = Counter(words_s2)

    Here, counter_s1 and counter_s2 act like dictionaries where each word is a key, and its count in the corresponding sentence is the value.

  3. Combine the counters: By adding these two Counter objects using the + operation, we obtain a single counter that contains the sum of word counts from both sentences:

    1combined_counter = counter_s1 + counter_s2

    In combined_counter, any word with a total count greater than 1 indicates that it is either repeated within the same sentence or present in both sentences.

  4. Filter out the uncommon words: Finally, we need to gather only those words that appear exactly once – which implies they're uncommon:

    1uncommon_words = [word for word, count in combined_counter.items() if count == 1]

    This list comprehension iterates over the items of combined_counter. For each word, it checks if the count is 1 (using if count == 1), and if so, the word is added to the list uncommon_words.

The full implementation of the function uncommonFromSentences as a method inside the Solution class is as follows:

1class Solution:
2    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
3        # Step 1 and 2: count word occurrences
4        cnt = Counter(s1.split()) + Counter(s2.split())
5        # Step 3 and 4: combine counts and filter uncommon words
6        return [word for word, count in cnt.items() if count == 1]

In conclusion, by utilizing the Counter data structure to perform frequency analysis and array comprehensions for filtering, the solution efficiently identifies all uncommon words with minimal code and avoids the need for handcrafting frequency calculations or manual comparisons between word lists.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Example Walkthrough

Let's consider two sentences as examples:

s1: "apple banana" s2: "banana orange apple"

Following the solution approach:

  1. Split the sentences into words: For s1: words_s1 = ['apple', 'banana'] For s2: words_s2 = ['banana', 'orange', 'apple']

    Both sentences are split into lists of individual words.

  2. Count the word occurrences: Here's what the Counter objects might look like: counter_s1 = Counter({'apple': 1, 'banana': 1}) counter_s2 = Counter({'banana': 1, 'orange': 1, 'apple': 1})

    Each word is now associated with its occurrence count in the sentences.

  3. Combine the counters: When combined, the counters reflect the total occurrence of each word: combined_counter = Counter({'apple': 2, 'banana': 2, 'orange': 1})

    This shows 'apple' and 'banana' each have a total count of 2, while 'orange' has a count of 1.

  4. Filter out the uncommon words: We want the words which have a count of exactly 1: uncommon_words = ['orange']

    Only 'orange' fulfills the criteria of being uncommon (appearing exactly once overall and not in both sentences).

Thus, with our example, the function uncommonFromSentences(s1, s2) would return ['orange'] as the list of uncommon words.

Solution Implementation

1from collections import Counter
2from typing import List
3
4class Solution:
5    def uncommonFromSentences(self, sentence1: str, sentence2: str) -> List[str]:
6        # Combine the word counts from both sentences
7        combined_counts = Counter(sentence1.split()) + Counter(sentence2.split())
8      
9        # Find and return the list of words that appear only once
10        return [word for word, count in combined_counts.items() if count == 1]
11
1class Solution {
2    public String[] uncommonFromSentences(String s1, String s2) {
3        // Create a Hash Map to store word counts
4        Map<String, Integer> wordCounts = new HashMap<>();
5      
6        // Split the first string by spaces and count the occurrences of each word
7        for (String word : s1.split(" ")) {
8            wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
9        }
10      
11        // Split the second string by spaces and count the occurrences of each word
12        for (String word : s2.split(" ")) {
13            wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
14        }
15      
16        // List to hold the words that occur exactly once
17        List<String> uniqueWords = new ArrayList<>();
18      
19        // Iterate through the entry set of wordCounts
20        for (Map.Entry<String, Integer> entry : wordCounts.entrySet()) {
21            // If a word count is exactly 1, it's uncommon, add to the list
22            if (entry.getValue() == 1) {
23                uniqueWords.add(entry.getKey());
24            }
25        }
26        // Return the unique words as an array of strings
27        return uniqueWords.toArray(new String[0]);
28    }
29}
30
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <sstream>
5using namespace std;
6
7class Solution {
8public:
9    vector<string> uncommonFromSentences(string A, string B) {
10        // Map to store the count of each word across both sentences
11        unordered_map<string, int> wordCount;
12
13        // Lambda function to parse each word in a sentence and update the word count
14        auto addWordsToCount = [&](const string& sentence) {
15            stringstream stream(sentence);
16            string word;
17            while (stream >> word) {
18                ++wordCount[word]; // Increment the word count for each word found
19            }
20        };
21
22        // Parse both sentences A and B to count the words
23        addWordsToCount(A);
24        addWordsToCount(B);
25
26        // Vector to store the result - the uncommon words from both sentences
27        vector<string> result;
28
29        // Iterate through the word count map
30        for (const auto& entry : wordCount) {
31            // If the word count is 1, that means it's an uncommon word
32            if (entry.second == 1) {
33                // Add it to the result list
34                result.emplace_back(entry.first);
35            }
36        }
37
38        return result; // Return the list of uncommon words
39    }
40};
41
1// This function takes two sentences as input and returns an array of words that appear
2// exactly once in either of the two sentences
3function uncommonFromSentences(sentence1: string, sentence2: string): string[] {
4    // Create a map to keep track of word counts across both sentences
5    const wordCounts: Map<string, number> = new Map();
6
7    // Split both sentences into words and combine them into a single array
8    // Then iterate over the array to count the occurrences of each word
9    for (const word of [...sentence1.split(' '), ...sentence2.split(' ')]) {
10        wordCounts.set(word, (wordCounts.get(word) || 0) + 1);
11    }
12
13    // Array to store the uncommon words (words that appear exactly once)
14    const uncommonWords: string[] = [];
15
16    // Iterate over the wordCounts map to find words with a count of 1
17    // These are the words that are unique to either sentence
18    for (const [word, count] of wordCounts.entries()) {
19        if (count === 1) {
20            uncommonWords.push(word);
21        }
22    }
23
24    // Return the array of uncommon words
25    return uncommonWords;
26}
27

Time and Space Complexity

Time Complexity

The time complexity of the provided code mainly involves three steps:

  1. The splitting of strings s1 and s2: This operation has a time complexity of O(N + M), where N is the length of s1 and M is the length of s2. The .split() method goes through each character in the strings.

  2. The creation of two Counter objects from the split results of s1 and s2: The Counter object creation from a list of words has a time complexity of O(K1 + K2), where K1 is the number of words in s1 and K2 is the number of words in s2. It counts the frequency of each word.

  3. Adding two Counter objects and filtering for uncommon words: The addition of two Counter objects is O(U), where U is the number of unique words across both s1 and s2. The list comprehension that follows iterates through the combined Counter object, which also has a complexity of O(U).

Thus, the overall time complexity of the code is O(N + M + U), where U <= K1 + K2 since U is the count of unique words in both s1 and s2.

Space Complexity

The space complexity is determined by:

  1. The lists created from splitting s1 and s2: This depends on the number of words in s1 and s2, which is O(K1 + K2).

  2. The Counter objects for s1 and s2: This also depends on the number of unique words, which would be O(U).

  3. The final list of uncommon words: In the worst-case scenario, all words are uncommon, which would also result in O(U) space complexity.

Since U <= K1 + K2, the overall space complexity can be described as O(K1 + K2).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄