920. Uncommon Words From Two Sentences¶

Difficulty: Easy

920. Uncommon Words from Two Sentences

Easy

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.

Solution¶

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        s1 += " "; s2 += " ";
        int n = s1.length(), m = s2.length();
        HashSet<String> first = new HashSet<>();
        HashSet<String> second = new HashSet<>();
        HashSet<String> firstR = new HashSet<>();
        HashSet<String> secondR = new HashSet<>();
        String current = "";
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) == ' ') {
                if (first.contains(current)) {
                    first.remove(current);
                    firstR.add(current);
                }
                if (!firstR.contains(current)) first.add(current);
                current = "";
            }
            else current += s1.charAt(i);
        }
        current = "";
        for (int i = 0; i < m; i++) {
            if (s2.charAt(i) == ' ') {
                if (second.contains(current)) {
                    secondR.add(current);
                    second.remove(current);
                }
                if (!secondR.contains(current)) second.add(current);
                current = "";
            }
            else current += s2.charAt(i);
        }
        ArrayList<String> res = new ArrayList<>();
        for (String temp : first) if (!second.contains(temp)) if (!res.contains(temp) && !firstR.contains(temp) && !secondR.contains(temp)) res.add(temp);
        for (String temp : second) if (!first.contains(temp)) if (!res.contains(temp) && !firstR.contains(temp) && !secondR.contains(temp)) res.add(temp);
        String answer[] = new String[res.size()];
        for (int i = 0; i < res.size(); i++) answer[i] = res.get(i);
        return answer;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here