884. 两句话中的不常见单词

🟢 🔖 哈希表 字符串 计数 🔗 力扣open in new window LeetCodeopen in new window

题目

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 theuncommon 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 ，返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。

示例 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 中的所有单词间均由单个空格分隔

解题思路

分割句子成单词：
- 将两个句子 s1 和 s2 按空格分割成单词数组。即，s1.split(' ') 和 s2.split(' ')。
统计每个单词出现的次数：
- 使用一个 Map 来记录每个单词在两个句子中出现的次数。
- 遍历 s1 中的每个单词，更新 Map 中该单词的计数。
- 同样，遍历 s2 中的每个单词，更新 Map 中该单词的计数。
筛选不常见的单词：
- 不常见的单词是只在一个句子中出现过的单词，因此它们在 Map 中的计数为 1。
- 遍历 Map 的所有键，筛选出计数为 1 的单词。
返回结果：
- 返回不常见的单词数组。

复杂度分析

时间复杂度：O(n + m)，其中 n 和 m 分别是 s1 和 s2 中的字符数。
- 分割句子并将其转化为单词数组的时间复杂度是 O(n + m)。
- 遍历单词数组并更新 Map 中每个单词的计数的时间复杂度是 O(n + m)。
- 筛选出计数为 1 的单词的时间复杂度是 O(k)，其中 k 是 Map 中的单词数量，最多为 n + m。
- 总时间复杂度是 O(n + m)。
空间复杂度：O(n + m)，使用一个 Map 来存储所有出现的单词，最坏情况下，Map 中可能会存储所有单词。

代码

/**
 * @param {string} s1
 * @param {string} s2
 * @return {string[]}
 */
var uncommonFromSentences = function (s1, s2) {
	let count = new Map(); // 用 Map 来统计每个单词出现的次数

	const words1 = s1.split(' '); // 分割句子 s1 为单词数组
	const words2 = s2.split(' '); // 分割句子 s2 为单词数组

	// 遍历 s1 中的单词，统计出现次数
	for (let word of words1) {
		count.set(word, (count.get(word) || 0) + 1);
	}

	// 遍历 s2 中的单词，统计出现次数
	for (let word of words2) {
		count.set(word, (count.get(word) || 0) + 1);
	}

	// 过滤出出现次数为 1 的单词
	return [...count.keys()].filter((key) => count.get(key) == 1);
};

884. 两句话中的不常见单词

# 884. 两句话中的不常见单词

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

884. 两句话中的不常见单词

题目

题目大意

解题思路

复杂度分析

代码

相关题目