跳至主要內容

771. 宝石与石头

771. 宝石与石头

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

题目

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;
};