Uncommon Words From Two Sentences - Leetcode Solution

Problem Statement: We are given two sentences A and B. A sentence is a string of space separated words. Each word consists only of lowercase letters. Every uncommon word in A and B should be outputted in a sorted order.

Solution: The problem requires us to find the uncommon words in two sentences A and B. A sentence can be treated as a string of space-separated words and the uncommon words refer to words that appear only in one of the sentences and not in the other. The approach to solving this problem involves splitting both sentences into words and counting the frequency of each word. This is followed by iterating over all the unique words and checking if they appear only once in the entire text using the frequency count.

Step 1: Split the words in both sentences The first step is to split the words in both sentences into individual words. This can be achieved using the split() function in Python.

Step 2: Count the frequency of each word The next step is to count the frequency of each word in both sentences. This can be achieved by using a dictionary data structure in Python. We iterate over all the words in both sentences and increment the count of the word in the dictionary.

Step 3: Iterate over all the unique words In this step, we iterate over all the unique words in both sentences and check if they appear only once in the entire text using the frequency count. We add such words to the resulting list.

Step 4: Sort the resulting list
Finally, we sort the resulting list in ascending order and return it.

Here's the Python code that implements this approach:

def uncommonFromSentences(A: str, B: str) -> List[str]:
    words_freq = {}  # empty dictionary to store the frequency count of words

    # Split the words in both sentences into a list
    A_words = A.split()
    B_words = B.split()

    # Loop over words in both sentences and update the frequency in the dictionary
    for word in A_words + B_words:
        words_freq[word] = words_freq.get(word, 0) + 1

    # Iterate over all the unique words and check if they appear only once in the entire text using the frequency count
    uncommon_words = [word for word in words_freq if words_freq[word] == 1]

    # Sort the resulting list
    uncommon_words.sort()

    return uncommon_words

Time Complexity: The above approach requires two loops to iterate over the words in both sentences and update the frequency in the dictionary. It also involves iterating over all the unique words in the dictionary to check if they appear only once in the entire text. Therefore, the time complexity of this approach is O(n) where n is the total number of words in both sentences.

Space Complexity: The space complexity of this approach is O(n) where n is the total number of words in both sentences. It requires additional space to store the frequency count of words in the dictionary.

1