Problem of The Day: Uncommon Words from Two Sentences

Problem Statement

Intuition

The task is to find words that appear exactly once in either of two sentences, but not in both. My first thought is to break each sentence into individual words, count the occurrences of each word, and then filter out the ones that appear more than once in either sentence or appear in both.

Approach

1. Split both sentences into words using the split() function.
2. Use Python’s Counter from the collections module to count the frequency of each word in both sentences.
3. Iterate through the words and their frequencies:
   • For words from the first sentence, if they appear only once and do not exist in the second sentence, add them to the result.
   • For words from the second sentence, do the same check as above (i.e., they appear once and do not exist in the first sentence or the result).
4. Return the list of uncommon words.

Complexity

• Time complexity: The time complexity is \(O(n + m)\), where \(n\) is the number of words in the first sentence, and \(m\) is the number of words in the second sentence. This is because we iterate through the words in both sentences and use the Counter to compute frequencies in linear time.

• Space complexity: The space complexity is \(O(n + m)\), where \(n\) is the number of words in the first sentence and \(m\) is the number of words in the second sentence. This accounts for storing the word counts and the result list.

Code

from collections import Counter
class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        c1 = Counter(s1.split())
        c2 = Counter(s2.split())
        res = []
        for w1, f1 in c1.items():
            if f1 == 1 and w1 not in c2:
                res.append(w1)
        for w2, f2 in c2.items():
            if f2 == 1 and w2 not in c1 and w2 not in res:
                res.append(w2)

        return res

Editorial

Approach 1: Counting

class Solution(object):
    def uncommonFromSentences(self, A, B):
        count = {}
        for word in A.split():
            count[word] = count.get(word, 0) + 1
        for word in B.split():
            count[word] = count.get(word, 0) + 1

        #Alternatively:
        #count = collections.Counter(A.split())
        #count += collections.Counter(B.split())

        return [word for word in count if count[word] == 1]

• time: O(m + n)
• space: O(m + n)