宝石与石头 图解题解

石头堆里数宝石，数的是哪些石头

jewels 里每个字符代表一种宝石，且种类互不相同；stones 里每个字符是你手上的一块石头。要数的是 stones 里有多少块，其种类正好也出现在 jewels 里。大小写算两种，「a」和「A」是不同的石头。题面给 jewels="aA"、stones="aAAbbbb"，输出 3——a、A、A 是宝石，四个 b 不是；再给 jewels="z"、stones="ZZ"，输出 0，大写 Z 和小写 z 不算一种。

每块石头都去宝石串里翻一遍，会慢成什么样

把每块石头拿去 jewels 里逐个字符比对，是能得出答案的。可 stones 有 n 块，jewels 有 m 个字符，最坏情况每块石头都要把 m 个宝石比到底，合起来 O(m×n) 次比对，一层套一层的双重循环。两个串都上万时，这就是上亿次比较，吃亏在同一个问题反复问：这块石头到底是不是宝石。

把宝石装进集合，查询为什么变成一步

既然瓶颈是「这块石头是不是宝石」被反复追问，那就让每次追问都便宜。先把 jewels 的字符一次性放进一个哈希集合，也就是 set。它底层靠散列定位，判断一个元素在不在里面是 O(1)，不随集合变大而变慢。集合建好后，每块石头只要问一句「在不在集合里」，一步就有答案，不必再逐个比。建集合扫一遍 jewels 是 O(m)，之后扫 stones 每块 O(1)，两段线性叠加就是 O(m+n)。

题面那串 aAAbbbb，逐块数下来是几

先把 jewels="aA" 装进集合，里面只有「a」「A」两种。再从头扫 stones="aAAbbbb"：第一块 a 在集合里，计数到 1；第二块 A 在，计数到 2；第三块 A 在，计数到 3；接下来四个 b 都不在集合里，计数停在 3，输出 3。换第二个例子，jewels="z" 的集合只有小写「z」，stones="ZZ" 两块都是大写 Z，集合里查不到，一次都没命中，输出 0。

大小写混作一团，z 就把 Z 认成自己人

最容易放反的是方向：该进集合的是种类唯一的 jewels，要计数的是 stones；若反过来把 stones 塞进集合再拿 jewels 去查，数出来的就不是石头块数了。大小写是道硬约束，「z」和「Z」是两个字符，只要照原字符建集合、照原字符查询，它们天生分开，怕的是有人先把两串统一转小写，那 Z 就被当成 z 多算进去。

复杂度上，建集合扫 jewels 一遍 O(m)、逐块查 stones 一遍 O(n)，合起来 O(m+n)；集合存 jewels 的字符是 O(m) 空间，若改用一个长度 128 的数组当集合（字符 ASCII 不超过 128），空间就固定成常数 O(1)。还有两种边界值得先过脑子：stones 每块都是宝石时，答案等于 stones 的长度；jewels 和 stones 毫无交集时，答案是 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        s = set(jewels)
        return sum(c in s for c in stones)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        int s[128] = {0};
        for (char c : jewels) {
            s[c] = 1;
        }
        int ans = 0;
        for (char c : stones) {
            ans += s[c];
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int[] s = new int[128];
        for (char c : jewels.toCharArray()) {
            s[c] = 1;
        }
        int ans = 0;
        for (char c : stones.toCharArray()) {
            ans += s[c];
        }
        return ans;
    }
}