Uncommon Words from Two Sentences

EASY

Description

A sentence is a string of single-space separated words where each word consists only of lowercase letters.

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Given two sentences s1 and s2, return a list of all the uncommon words. You may return the answer in any order.

Example 1:

Input: s1 = "this apple is sweet", s2 = "this apple is sour"

Output: ["sweet","sour"]

Explanation:

The word "sweet" appears only in s1, while the word "sour" appears only in s2.

Example 2:

Input: s1 = "apple apple", s2 = "banana"

Output: ["banana"]

Constraints:

1 <= s1.length, s2.length <= 200
s1 and s2 consist of lowercase English letters and spaces.
s1 and s2 do not have leading or trailing spaces.
All the words in s1 and s2 are separated by a single space.

Approaches

Checkout 2 different approaches to solve Uncommon Words from Two Sentences. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

This approach involves combining both sentences and then iterating through the list of words. For each word, a second, nested loop is used to count its total occurrences. If the count is exactly one, the word is considered uncommon. This method is straightforward but computationally expensive.

Algorithm

Concatenate s1 and s2 with a space in between to form a single string.
Split the combined string by spaces to get an array of all words.
Initialize an empty list result to store the uncommon words.
Iterate through the array of words with an outer loop (let's say index i).
For each word words[i], start an inner loop (index j) to iterate through the entire array again.
Inside the inner loop, count how many times words[i] appears in the array.
After the inner loop finishes, if the count for words[i] is 1, add it to the result list.
Finally, convert the result list to a string array and return it.

The core idea is to first create a single collection of all words from both sentences. Then, for every single word in this collection, we perform a full scan of the collection to count how many times it appears. A word is added to our final list of uncommon words only if its total count is exactly one. This brute-force check is performed for every word.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        String[] words = (s1 + " " + s2).split(" ");
        List<String> result = new ArrayList<>();
        
        for (int i = 0; i < words.length; i++) {
            int count = 0;
            for (int j = 0; j < words.length; j++) {
                if (words[i].equals(words[j])) {
                    count++;
                }
            }
            if (count == 1) {
                // To avoid duplicates in the result list, we can check before adding
                if (!result.contains(words[i])) {
                    result.add(words[i]);
                }
            }
        }
        
        return result.toArray(new String[0]);
    }
}

Note: The provided code can be slightly optimized by using a Set to store results to handle duplicates automatically, but the core O(L^2) complexity remains.

Complexity Analysis

Time Complexity: O(L^2 * W), where `L` is the total number of words in both sentences and `W` is the maximum length of a word. The nested loops cause the quadratic time complexity, and each string comparison takes O(W) time.Space Complexity: O(L * W), where `L` is the total number of words and `W` is the maximum length of a word. This space is required to store the combined array of words and the result list.

Pros and Cons

Pros:

Simple to understand and implement without requiring knowledge of advanced data structures.

Cons:

Very inefficient due to the O(L^2) time complexity, where L is the total number of words.
Will likely result in a 'Time Limit Exceeded' error for larger inputs.

Code Solutions

Checking out 4 solutions in different languages for Uncommon Words from Two Sentences. Click on different languages to view the code.

class Solution {
public
  String[] uncommonFromSentences(String s1, String s2) {
    Map<String, Integer> cnt = new HashMap<>();
    for (String s : s1.split(" ")) {
      cnt.put(s, cnt.getOrDefault(s, 0) + 1);
    }
    for (String s : s2.split(" ")) {
      cnt.put(s, cnt.getOrDefault(s, 0) + 1);
    }
    List<String> ans = new ArrayList<>();
    for (var e : cnt.entrySet()) {
      if (e.getValue() == 1) {
        ans.add(e.getKey());
      }
    }
    return ans.toArray(new String[0]);
  }
}

Video Solution

Watch the video walkthrough for Uncommon Words from Two Sentences

Patterns:

Counting

Data Structures:

Hash TableString