algoadvance

Leetcode 884. Uncommon Words from Two Sentences

Problem Statement

Given two sentences s1 and s2, return a list of all the uncommon words. Uncommon words are those words that appear exactly once in one of the sentences, and do not appear in the other sentence.

Clarifying Questions

1. Input Format: Are the sentences guaranteed to be non-empty strings?
   • Yes, the problem guarantees non-empty string inputs.
2. Character Constraints: Are the sentences case-sensitive? e.g., is “Apple” different from “apple”?
   • Yes, the comparison is case-sensitive according to typical string comparison rules in Java.
3. Word Delimiters: Are words separated by spaces only?
   • Yes, words are separated by single spaces, as per the typical interpretation of a sentence in such problems.
4. Output Order: Does the order of words in the output list matter?
   • No, the order of uncommon words in the output list does not matter.

Strategy

1. Tokenization: Split both sentences into words.
2. Count Frequency: Use a HashMap to count the frequency of each word from both sentences.
3. Identify Uncommon Words: Extract words that have a frequency of exactly one and only occur in one of the sentences.
4. Edge Cases: Handle cases where all words are common between the two sentences.

Code

Here’s how you can implement the problem in Java:

import java.util.*;

public class UncommonWords {
    public static String[] uncommonFromSentences(String s1, String s2) {
        // Split both sentences into words
        String[] words1 = s1.split(" ");
        String[] words2 = s2.split(" ");
        
        // Use a HashMap to count the frequency of each word
        Map<String, Integer> wordCount = new HashMap<>();
        
        for (String word : words1) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        
        for (String word : words2) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        
        // List to hold the uncommon words
        List<String> uncommonWords = new ArrayList<>();
        
        for (Map.Entry<String, Integer> entry : wordCount.entrySet()) {
            if (entry.getValue() == 1) {
                uncommonWords.add(entry.getKey());
            }
        }
        
        // Convert list to array
        return uncommonWords.toArray(new String[0]);
    }

    public static void main(String[] args) {
        // Test cases
        String s1 = "this apple is sweet";
        String s2 = "this apple is sour";
        System.out.println(Arrays.toString(uncommonFromSentences(s1, s2))); // Output: ["sweet", "sour"]

        s1 = "apple apple";
        s2 = "banana";
        System.out.println(Arrays.toString(uncommonFromSentences(s1, s2))); // Output: ["banana"]
    }
}

Time Complexity

• Tokenization: O(n + m), where n and m are the number of characters in s1 and s2, respectively.
• Counting Frequency: O(w1 + w2), where w1 and w2 are the number of words in s1 and s2, respectively.
• Identifying Uncommon Words: O(w1 + w2), iterating through the dictionary keys.
• Overall Time Complexity: O(n + m), as tokenization, counting, and extracting uncommon words are all linear operations proportional to the total input size.

Space Complexity

• HashMap Storage: O(w1 + w2), where w1 and w2 are the number of distinct words in s1 and s2.
• Output List: In the worst case, all words could be uncommon, O(w1 + w2).
• Auxiliary Space: The space needed for storing the split words and the results.
• Overall Space Complexity: O(w1 + w2).

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?