algoadvance

Leetcode 884. Uncommon Words from Two Sentences

Problem Statement

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

Clarifying Questions

1. Input constraints:
   • Can the input sentences be empty?
   • What is the maximum length of each sentence?
   • Are there any restrictions on the characters in the sentences?
2. Output specifics:
   • Should the order of uncommon words in the output list follow any specific order, e.g., sorted?

Given these questions, let’s assume:

• Sentences are non-empty.
• Sentences contain only lowercase English letters and spaces.
• We do not need to sort the output list. It can be in any order.

Strategy

1. Count Word Frequencies:
   • Use a hash map (unordered_map in C++) to count the frequency of each word in both sentences.
2. Identify Uncommon Words:
   • Once we have the word frequencies, iterate through the map and collect words that appear exactly once.

Code

Here’s the implementation in C++:

#include <vector>
#include <string>
#include <sstream>
#include <unordered_map>

using namespace std;

vector<string> uncommonFromSentences(string s1, string s2) {
    unordered_map<string, int> word_count;
    stringstream ss(s1 + " " + s2);
    string word;
    
    // Count the frequency of each word
    while (ss >> word) {
        word_count[word]++;
    }

    // Collect words that appear exactly once
    vector<string> result;
    for (const auto& entry : word_count) {
        if (entry.second == 1) {
            result.push_back(entry.first);
        }
    }
    
    return result;
}

// Example usage
int main() {
    string s1 = "this apple is sweet";
    string s2 = "this apple is sour";
    vector<string> uncommon_words = uncommonFromSentences(s1, s2);
    
    for (const string& word : uncommon_words) {
        cout << word << " ";
    }
    return 0;
}

Time Complexity

• Word Counting: We traverse each word in both sentences combined, which is an O(n) operation where n is the total number of characters in s1 + s2.
• Frequency Map Construction: Updating the unordered_map for each word also takes average O(1) time.
• Collecting Uncommon Words: Iterating over the hash map entries takes O(m) time where m is the number of unique words.

Overall time complexity is: [ O(n + m) ] where n is the length of the combined sentences and m is the number of unique words.

Space Complexity

• We use extra space for the unordered_map to store word frequencies, which will be at most O(m) where m is the number of unique words.
• The additional space for the resulting list of uncommon words also comes from the total number of unique words.

Thus, the space complexity is: [ O(m) ]

This solution should efficiently handle the problem within the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?