771. 宝石与石头

🟢   🔖  哈希表 字符串  🔗 力扣 LeetCode

题目

You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: jewels = "aA", stones = "aAAbbbb"

Output: 3

Example 2:

Input: jewels = "z", stones = "ZZ"

Output: 0

Constraints:

• 1 <= jewels.length, stones.length <= 50
• jewels and stones consist of only English letters.
• All the characters of jewels are unique.

题目大意

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

示例 1：

输入： jewels = "aA", stones = "aAAbbbb"

输出： 3

示例 2：

输入： jewels = "z", stones = "ZZ"

输出： 0****

提示：

• 1 <= jewels.length, stones.length <= 50
• jewels 和 stones 仅由英文字母组成
• jewels 中的所有字符都是 唯一的

解题思路

1. 利用 Set 存储宝石类型：

   • jewels 的字符是独特的，因此可以使用 Set 来快速查找某个字符是否是宝石类型。
   • 将 jewels 转换成一个 Set，以便进行快速查找操作。

2. 遍历 stones：

   • 遍历 stones 中的每个字符。
   • 对于每个字符，检查它是否存在于 Set 中：
     • 如果存在，则计数器加一。
     • 如果不存在，则跳过。

3. 返回结果：

   • 遍历结束后，返回计数器的值，即为宝石的总数。

复杂度分析

• 时间复杂度：O(J + S)，其中 J 是 jewels 的长度，S 是 stones 的长度。

  • 将 jewels 转换为 Set 的时间复杂度为 O(J)。
  • 遍历 stones 的时间复杂度为 O(S)。
  • 因此总的时间复杂度为 O(J + S)。

• 空间复杂度：O(J)

  • 存储 Set 的空间复杂度为 O(J)，因为 Set 的大小最多与 jewels 的长度相同；
  • 其他变量（如计数器）占用常量空间；
  • 因此总的空间复杂度为 O(J)。

代码

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function (jewels, stones) {
	// 将 jewels 转换为 Set
	const set = new Set(jewels.split(''));

	// 初始化计数器
	let count = 0;

	// 遍历 stones
	for (let char of stones) {
		// 如果字符是宝石
		if (set.has(char)) {
			count++; // 计数器加一
		}
	}

	// 返回计数器
	return count;
};