771. 宝石与石头
题目描述
输入两个字符串 jewels 和 stones。jewels 中每个字符代表一种属于宝石的石头类型，这些字符互不相同。stones 中每个字符代表你手里的一块石头及其类型。
返回你手里的石头中有多少块是宝石。大小写敏感，a 和 A 是两种不同的类型。
示例 1
输入：jewels = "aA", stones = "aAAbbbb" 输出：3
解释：stones 中的 1 个 a 和 2 个 A 都是宝石。
示例 2
输入：jewels = "z", stones = "ZZ" 输出：0
解释：宝石类型是小写 z，大写 Z 不算。
数据范围
1 <= jewels.length, stones.length <= 50jewels和stones只含英文字母。jewels中没有重复字符。
解题思路
先把 jewels 里的字符放进一个哈希集合，这样判断一块石头是不是宝石只需 O(1)。再遍历 stones，每遇到集合里的字符就把计数加 1。
为什么正确
处理完 stones 的前 i 个字符时，count 等于其中属于 jewels 的字符个数。
复杂度分析
时间 O(|jewels| + |stones|)，额外空间 O(|jewels|)。
易错点
每块石头都在 jewels 里逐个查找会变成 O(|jewels| · |stones|)。还要注意大小写敏感，不要把字符统一转成小写。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
jewel_set = set(jewels)
count = 0
for s in stones:
if s in jewel_set:
count += 1
return countclass Solution {
public int numJewelsInStones(String jewels, String stones) {
Set<Character> jewelSet = new HashSet<>();
for (char c : jewels.toCharArray()) jewelSet.add(c);
int count = 0;
for (char s : stones.toCharArray()) {
if (jewelSet.contains(s)) {
count += 1;
}
}
return count;
}
}class Solution {
public:
int numJewelsInStones(string jewels, string stones) {
unordered_set<char> jewelSet(jewels.begin(), jewels.end());
int count = 0;
for (char s : stones) {
if (jewelSet.count(s)) {
count += 1;
}
}
return count;
}
};func numJewelsInStones(jewels string, stones string) int {
jewelSet := map[rune]bool{}
for _, c := range jewels {
jewelSet[c] = true
}
count := 0
for _, s := range stones {
if jewelSet[s] {
count += 1
}
}
return count
}var numJewelsInStones = function(jewels, stones) {
const jewelSet = new Set(jewels);
let count = 0;
for (const s of stones) {
if (jewelSet.has(s)) {
count += 1;
}
}
return count;
};function numJewelsInStones(jewels: string, stones: string): number {
const jewelSet = new Set<string>(jewels);
let count = 0;
for (const s of stones) {
if (jewelSet.has(s)) {
count += 1;
}
}
return count;
}