What is the best approach to solve 'Uncommon Words from Two Sentences'?

The most efficient way to solve this problem is by using hash tables to count the frequency of each word in both sentences and then filtering out the uncommon ones.

How do I filter uncommon words from two sentences?

After counting the word frequencies, filter the words that appear exactly once in one sentence and not in the other.

What data structures can I use to solve the problem?

Hash tables are ideal for this problem as they allow efficient counting and filtering of words.

What is the time complexity of this problem?

The time complexity is O(M + N), where M and N are the lengths of the two sentences.

Can I optimize the solution for large inputs?

Yes, you can optimize the solution by considering more advanced data structures or parallelizing the word counting process.

#884

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

两句话中的不常见单词

句子是一串由空格分隔的单词。每个单词仅由小写字母组成。如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的。给你两个句子 s1 和 s2 ，返回所有不常用单词的列表。返回列表中单词可以按任意顺序组织。示例 1：输入： s1 = …

哈希表字符串计数

题目描述

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

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

给你两个句子 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 <= 200
s1 和 s2 由小写英文字母和空格组成
s1 和 s2 都不含前导或尾随空格
s1 和 s2 中的所有单词间均由单个空格分隔

lightbulb

解题思路

方法一：哈希表

根据题目描述，只要单词出现一次，就符合题目要求。因此，我们用哈希表 $cnt$ 记录所有单词以及出现的次数。

然后遍历哈希表，取出所有出现次数为 $1$ 的字符串即可。

时间复杂度 $O(m + n)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 和 $n$ 分别是字符串 $s1$ 和 $s2$ 的长度。

1

2

3

4

5

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        cnt = Counter(s1.split()) + Counter(s2.split())
        return [s for s, v in cnt.items() if v == 1]

speed

复杂度分析

指标	值
时间	O(M + N)
空间	O(M + N)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of hash tables for counting word frequencies.
question_mark
The candidate should be able to implement the filtering of uncommon words efficiently.
question_mark
The candidate should be aware of handling edge cases, like repeated words within a sentence.

warning

常见陷阱

外企场景

error
Not correctly handling words that appear more than once in either sentence.
error
Failing to account for cases where no uncommon words exist.
error
Incorrectly counting words, missing one of the sentences, or not using hash tables properly for counting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to return words that appear exactly twice in each sentence.
arrow_right_alt
Handle cases where multiple uncommon words exist but with a higher frequency.
arrow_right_alt
Optimize the solution for larger datasets by considering more advanced data structures.

help

常见问题

外企场景

继续练习

#819 最常见的单词 #811 子域名访问计数 #767 重构字符串