algoadvance

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

Example:

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

Clarifying Questions

1. What are the constraints on the length of the sentences?
   • Sentences are likely to be reasonably short due to typical input limits in coding challenges.
2. Are the words in the sentences case-sensitive?
   • The problem implicitly assumes case-sensitivity since there are no instructions to standardize case.
3. What are the word delimiters in the sentences?
   • Words are typically separated by spaces in a sentence.
4. Will there be any punctuation in the sentences?
   • The example provided involves punctuation-free sentences, suggesting we can assume no punctuation for simplicity.
5. How should we treat empty sentences?
   • If a sentence is empty, it has no uncommon words by definition.

Strategy

1. Split each sentence into words:
   • Use Python’s str.split() method to break sentences into lists of words.
2. Count occurrences of each word:
   • Utilize a dictionary (or collections.Counter) to count the occurrences of each word across both sentences.
3. Find uncommon words:
   • A word is uncommon if it occurs exactly once in the combined words of both sentences.
4. Filter out these words:
   • Construct a list of words that occur exactly once in the combined dataset.

Code

from collections import Counter

def uncommonFromSentences(s1, s2):
    # Split the sentences into words
    words_s1 = s1.split()
    words_s2 = s2.split()
    
    # Count the occurrences of each word
    word_count = Counter(words_s1 + words_s2)
    
    # Extract words which have exactly one occurrence
    uncommon_words = [word for word, count in word_count.items() if count == 1]
    
    return uncommon_words

# Example usage:
s1 = "this apple is sweet"
s2 = "this apple is sour"
print(uncommonFromSentences(s1, s2))  # Output: ["sweet", "sour"]

Time Complexity

• Splitting sentences into words:
  • O(n + m) where n is the length of s1 and m is the length of s2.
• Counting word occurrences:
  • Also O(n + m) because each word insertion/check in hashmap is O(1) on average, and we have n + m words in total.
• Filtering uncommon words:
  • This involves iterating over the hashmap, which has at most n + m entries resulting in O(n + m).

Therefore, the overall time complexity is O(n + m). The space complexity is also O(n + m) due to the storage used for splitting words and the hashmap for counting occurrences.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?