We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Uncommon Words from Two Sentences

Number: 920

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given two sentences s1 and s2, return a list of all the uncommon words. A word is considered uncommon if it appears exactly once in one sentence and does not appear in the other. Each sentence is a string of single-space separated words.

Key Insights

  • Split each sentence into words using space as a delimiter.
  • Use a hash table to count the frequency of each word across both sentences.
  • Identify the uncommon words by filtering those that have a frequency of exactly one.
  • This approach is efficient given the constraint of relatively short sentences.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the number of words in s1 and s2 respectively. Space Complexity: O(k), where k is the number of distinct words across both sentences.

Solution

The solution splits both sentences into their constituent words and uses a hash map to count the occurrence of each word. After building the frequency table, the algorithm iterates through the map to retrieve all words that have a frequency of 1. These words are the uncommon words as defined by the problem. The use of a hash map allows for efficient insertion and lookup, ensuring that the solution remains optimal.

Code Solutions

# Python solution

def uncommonFromSentences(s1, s2):
    # Split sentences into words and combine them into one list
    words = s1.split() + s2.split()
    # Create a dictionary to count frequency of each word
    frequency = {}
    for word in words:
        frequency[word] = frequency.get(word, 0) + 1
    # Collect words that appear exactly once
    result = [word for word, count in frequency.items() if count == 1]
    return result

# Example usage
s1 = "this apple is sweet"
s2 = "this apple is sour"
print(uncommonFromSentences(s1, s2))  # Expected output: ['sweet', 'sour']
← Back to All Questions