What is the optimal time complexity for this problem?

The optimal time complexity is O(N), where N is the length of the stones string, as each stone is checked exactly once.

How do we handle case sensitivity in this problem?

Case sensitivity is handled by treating uppercase and lowercase letters as different characters. For example, 'a' and 'A' are distinct.

What data structure should we use for storing jewels?

A hash set is ideal for storing jewels because it allows O(1) average time complexity for membership checks.

How do we count how many stones are jewels?

We iterate through the stones string and check if each stone is present in the jewels hash set, incrementing the count each time.

What if the stones string is empty?

If the stones string is empty, the output will be 0 since there are no stones to match with jewels.

#771

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

宝石与石头

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。示例 1：输入： jewels = "aA…

哈希表字符串

题目描述

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

lightbulb

解题思路

方法一：哈希表或数组

我们可以先用一个哈希表或数组 $s$ 记录所有宝石的类型。然后遍历所有石头，如果当前石头是宝石，就将答案加一。

时间复杂度 $O(m+n)$ ，空间复杂度 $O(|\Sigma|)$ ，其中 $m$ 和 $n$ 分别是字符串 $jewels$ 和 $stones$ 的长度，而 $\Sigma$ 是字符集，本题中字符集为所有大小写英文字母的集合。

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	complexity is O(N) where N is the length of the stones string, due to the iteration over stones. Space complexity is O(M) where M is the number of unique jewels, as we use a hash set to store jewels.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for candidates who can efficiently use hash tables for set membership checks.
question_mark
Watch for candidates who consider edge cases like empty strings or case sensitivity.
question_mark
Evaluate how quickly the candidate identifies the need for a hash set given the unique character constraint.

warning

常见陷阱

外企场景

error
Overcomplicating the solution with unnecessary data structures instead of using a hash set for jewels.
error
Failing to account for case sensitivity when checking if a stone is a jewel.
error
Ignoring edge cases like when there are no jewels or no stones.

swap_horiz

进阶变体

外企场景

arrow_right_alt
If the jewels string contains repeated characters, candidates must adjust the approach accordingly.
arrow_right_alt
The problem can be adjusted to handle larger input sizes, testing the solution's scalability.
arrow_right_alt
The problem could be expanded by requiring the return of the list of jewel stones rather than just the count.

help

常见问题

外企场景

继续练习

#770 基本计算器 IV #767 重构字符串 #763 划分字母区间