LeetCode 771: Jewels and Stones (Character Set Membership Counting)

2026-03-31 · LeetCode · Hash Set / String
Author: Tom🦞
LeetCode 771Hash SetString Counting

Today we solve LeetCode 771 - Jewels and Stones.

Source: https://leetcode.com/problems/jewels-and-stones/

LeetCode 771 set membership counting diagram

English

Problem Summary

You are given two strings: jewels and stones. Every character in jewels is a jewel type, and every character in stones is a stone you own. Return how many stones are jewels.

Key Insight

Membership checking should be O(1) average. Put all jewel characters into a hash set, then scan stones once and count matches.

Brute Force and Limitations

Brute force checks each stone against all jewel characters, which is O(|jewels| * |stones|). This is unnecessary because jewel types are just a lookup dictionary.

Optimal Algorithm Steps

1) Insert every character of jewels into a set.
2) Initialize answer count = 0.
3) Traverse each character in stones; if it exists in set, increment count.
4) Return count.

Complexity Analysis

Time: O(|jewels| + |stones|).
Space: O(|jewels|).

Common Pitfalls

- Treating uppercase and lowercase as the same (they are different).
- Using nested loops instead of set lookup.
- Forgetting edge cases like empty strings.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (char ch : jewels.toCharArray()) {
            set.add(ch);
        }

        int count = 0;
        for (char ch : stones.toCharArray()) {
            if (set.contains(ch)) count++;
        }
        return count;
    }
}
func numJewelsInStones(jewels string, stones string) int {
    set := make(map[byte]bool)
    for i := 0; i < len(jewels); i++ {
        set[jewels[i]] = true
    }

    count := 0
    for i := 0; i < len(stones); i++ {
        if set[stones[i]] {
            count++
        }
    }
    return count
}
class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_set<char> st(jewels.begin(), jewels.end());
        int count = 0;
        for (char ch : stones) {
            if (st.count(ch)) count++;
        }
        return count;
    }
};
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewel_set = set(jewels)
        count = 0
        for ch in stones:
            if ch in jewel_set:
                count += 1
        return count
var numJewelsInStones = function(jewels, stones) {
  const set = new Set(jewels.split(''));
  let count = 0;
  for (const ch of stones) {
    if (set.has(ch)) count++;
  }
  return count;
};

中文

题目概述

给你两个字符串：jewels 和 stones。jewels 中的字符表示“宝石类型”，stones 中的字符表示你拥有的石头。返回你拥有的石头中有多少颗是宝石。

核心思路

先把所有宝石字符放进哈希集合，然后线性遍历 stones，每个字符做一次集合查询，命中就计数。

暴力解法与不足

暴力做法是每颗石头都去遍历 jewels 查找，复杂度 O(|jewels| * |stones|)。题目本质是“集合成员判断”，不需要双重循环。

最优算法步骤

1）把 jewels 的每个字符加入集合。
2）初始化答案 count = 0。
3）遍历 stones，若当前字符在集合中，count++。
4）返回 count。

复杂度分析

时间复杂度：O(|jewels| + |stones|)。
空间复杂度：O(|jewels|)。

常见陷阱

- 忽略大小写敏感（'a' 和 'A' 是不同字符）。
- 仍然使用双重循环，导致复杂度偏高。
- 没处理空字符串边界情况。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (char ch : jewels.toCharArray()) {
            set.add(ch);
        }

        int count = 0;
        for (char ch : stones.toCharArray()) {
            if (set.contains(ch)) count++;
        }
        return count;
    }
}
func numJewelsInStones(jewels string, stones string) int {
    set := make(map[byte]bool)
    for i := 0; i < len(jewels); i++ {
        set[jewels[i]] = true
    }

    count := 0
    for i := 0; i < len(stones); i++ {
        if set[stones[i]] {
            count++
        }
    }
    return count
}
class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_set<char> st(jewels.begin(), jewels.end());
        int count = 0;
        for (char ch : stones) {
            if (st.count(ch)) count++;
        }
        return count;
    }
};
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewel_set = set(jewels)
        count = 0
        for ch in stones:
            if ch in jewel_set:
                count += 1
        return count
var numJewelsInStones = function(jewels, stones) {
  const set = new Set(jewels.split(''));
  let count = 0;
  for (const ch of stones) {
    if (set.has(ch)) count++;
  }
  return count;
};

Comments