[LeetCode] 884. Uncommon Words from Two Sentences

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.

两句话中的不常见单词。

句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。

如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却 没有出现 ，那么这个单词就是 不常见的 。

给你两个 句子 s1 和 s2 ，返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。

思路

题意是让我们找某些单词，这些单词需要在其中一个句子中恰好出现一次，在另一个句子中却没有出现。这个条件等同于这些要找的单词在全局只出现一次。

我们可以用一个HashMap来统计每个单词出现的次数，然后遍历两个句子，统计每个单词出现的次数，如果出现次数为1，则加入到结果集中。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : s1.split(" ")) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        for (String word : s2.split(" ")) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        List<String> list = new ArrayList<>();
        for (String word : s1.split(" ")) {
            if (map.get(word) == 1) {
                list.add(word);
            }
        }
        for (String word : s2.split(" ")) {
            if (map.get(word) == 1) {
                list.add(word);
            }
        }

        int n = list.size();
        String[] res = list.toArray(new String[n]);
        return res;
    }
}