Solution Explanation: Uncommon Words from Two Sentences

This problem asks us to find words that appear exactly once in either of two input sentences (s1 and s2) but not in the other. The most efficient approach uses a hash table (or dictionary in Python) to count the occurrences of each word across both sentences.

Algorithm:

1. Tokenize: Split both input strings (s1 and s2) into individual words using space as the delimiter.

2. Count Occurrences: Use a hash table (e.g., HashMap in Java, Counter in Python, Map in JavaScript) to store each word and its frequency. Iterate through the words from both sentences, incrementing the count for each word encountered.

3. Filter Uncommon Words: Iterate through the hash table. If a word's count is exactly 1, it's an uncommon word and should be added to the result list.

4. Return Result: Return the list of uncommon words.

Time Complexity: O(m + n), where 'm' and 'n' are the number of words in s1 and s2 respectively. This is because we iterate through each word once to count occurrences and once more to filter uncommon words. The hash table lookups are considered O(1) on average.

Space Complexity: O(m + n) in the worst case, as the hash table could store all unique words from both sentences.

Code Examples (with explanations):

Python:

from collections import Counter
 
class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        """
        Finds uncommon words in two sentences using a Counter (hash table).
 
        Args:
          s1: The first sentence.
          s2: The second sentence.
 
        Returns:
          A list of uncommon words.
        """
        # Concatenate the words from both sentences and count occurrences.
        word_counts = Counter(s1.split() + s2.split())  
        
        #Filter words with count 1
        uncommon_words = [word for word, count in word_counts.items() if count == 1]
        return uncommon_words
 

Java:

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
 
class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        Map<String, Integer> wordCounts = new HashMap<>();
 
        // Count word occurrences in both sentences.
        for (String word : s1.split(" ")) {
            wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
        }
        for (String word : s2.split(" ")) {
            wordCounts.put(word, wordCounts.getOrDefault(word, 0) + 1);
        }
 
        List<String> uncommonWords = new ArrayList<>();
        // Add uncommon words to the result list.
        for (Map.Entry<String, Integer> entry : wordCounts.entrySet()) {
            if (entry.getValue() == 1) {
                uncommonWords.add(entry.getKey());
            }
        }
 
        return uncommonWords.toArray(new String[0]); 
    }
}

The other language examples (C++, Go, TypeScript, Rust, Javascript) follow a similar pattern: they tokenize the sentences, count word frequencies using a hash map or equivalent data structure, and then filter for words with a count of 1. The core logic remains consistent across all implementations.