884. 两句话中的不常见单词 : 数据结构模拟题

题目描述

这是 LeetCode 上的 884. 两句话中的不常见单词 ，难度为 简单。

Tag : 「模拟」、「哈希表」

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

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

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

示例 1：

输入：s1 = "this apple is sweet", s2 = "this apple is sour"
输出：["sweet","sour"]
复制代码

示例 2：

输入：s1 = "apple apple", s2 = "banana"
输出：["banana"]
复制代码

提示：

• 1 <= s1.length, s2.length <= 2001<=s1.length,s2.length<=200
• s1 和 s2 由小写英文字母和空格组成
• s1 和 s2 都不含前导或尾随空格
• s1 和 s2 中的所有单词间均由单个空格分隔

数据结构 + 模拟

根据题意进行模拟即可，先使用「哈希表」对两字符串进行「词频统计」，然后分别从两边的「哈希表」出发，统计符合题意的字符串数量。

或是利用某个单词在一边出现一次，另外一边不曾出现，等价于「某个单词总共只出现一次」。

代码：

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        Map<String, Integer> map = new HashMap<>();
        String str = s1 + " " + s2;
        String[] ss = str.split(" ");
        for (String s : ss) map.put(s, map.getOrDefault(s, 0) + 1);
        List<String> list = new ArrayList<>();
        for (String s : map.keySet()) if (map.get(s) == 1) list.add(s);
        return list.toArray(new String[list.size()]);
    }
}
复制代码

• 时间复杂度：令 n 和 m 分别为两字符串长度，复杂度为 O(n + m)O(n+m)
• 空间复杂度：O(n + m)O(n+m)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.884 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。