Easy

题目描述

给你一个字符串 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 中的所有字符都是唯一的

解题思路

这道题目要求统计 stones 中有多少个字符属于 jewels 中定义的宝石类型。

思路分析：

最直观的方法是对每个石头字符，检查它是否在宝石类型中。有以下几种常见解法：

  1. 暴力查找法：对 stones 中的每个字符，在 jewels 中线性查找是否存在。时间复杂度 O(m×n)。

  2. 哈希表法（推荐）：先将 jewels 中所有字符存入哈希集合，然后遍历 stones，对每个字符进行 O(1) 的查找。这是最优解法，时间复杂度 O(m+n)。

  3. 位运算优化：由于只有英文字母，可以用两个 64 位整数分别表示大小写字母的存在情况，但实现复杂度较高。

哈希表法是最佳选择，既简洁又高效。我们创建一个集合存储所有宝石类型，然后遍历石头字符串，统计属于宝石的石头数量。

代码实现

class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_set<char> jewelSet(jewels.begin(), jewels.end());
        int count = 0;
        for (char stone : stones) {
            if (jewelSet.count(stone)) {
                count++;
            }
        }
        return count;
    }
};

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewel_set = set(jewels)
        return sum(stone in jewel_set for stone in stones)

public class Solution {
    public int NumJewelsInStones(string jewels, string stones) {
        HashSet<char> jewelSet = new HashSet<char>(jewels);
        int count = 0;
        foreach (char stone in stones) {
            if (jewelSet.Contains(stone)) {
                count++;
            }
        }
        return count;
    }
}

var numJewelsInStones = function(jewels, stones) {
    const jewelSet = new Set(jewels);
    let count = 0;
    for (const stone of stones) {
        if (jewelSet.has(stone)) {
            count++;
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表法暴力查找法
时间复杂度O(m + n)O(m × n)
空间复杂度O(m)O(1)

其中 m 为 jewels 的长度，n 为 stones 的长度。