Jewels and Stones
你会得到两个由字母组成的字符串。jewels 中的每个字母代表一种珠宝，而且没有重复字母。stones 中的每个字母代表你拥有的一块石头。返回你的石头中有多少块是珠宝。字母区分大小写："a" 和 "A" 代表不同种类。
函数
- jewelsstring
- 哪些类型的石头算作宝石，每种用一个字母表示
- stonesstring
- 你拥有的石头，每个用一个字母表示
- 返回值integer
- 其字母出现在宝石中的石头数量
约束条件
1 ≤ jewels.length ≤ 521 ≤ stones.length ≤ 104- 这两个字符串只包含英文字母，包括小写和大写字母。
jewels中的字母各不相同。
示例
- 输入
- jewels = "rR"stones = "rubyRRr"
- 输出
- 4
- 解释
- 宝石种类是
r和R。在rubyRRr中，宝石r、R、R和r匹配，而u、b和y不匹配，所以答案是4。
- 输入
- jewels = "z"stones = "ZZZ"
- 输出
- 0
- 解释
- 唯一的宝石种类是小写字母
z。每块石头都是大写字母Z，属于另一种，因此都不算。
提示
逐个打开提示，每个都会多透露一点。
对于一块石头，哪个问题决定它是否计入？
你会对每块石头问一次“这封信是宝石吗？”。哪种数据结构能在常数时间内回答这个问题？
将
jewels中的字母放入集合，然后遍历stones，统计集合中包含的每个字母。保持大小写不变。
题解
对于每块石头，你都要问一个问题：这个字母是宝石吗？每次都在 jewels 字符串中搜索一遍石头，会重复相同的扫描。先把宝石字母放进集合中，这样每块石头只需查找一次。
扫描珠宝，找出每一颗宝石
思路
对于每颗石头，遍历 jewels，遇到第一个相同的字母时就停止；如果匹配，计数就加上 1。停在这里是安全的，因为宝石字母都不相同，所以每颗石头最多匹配其中一个字母。在第一个示例中，石头 u 会与 r 和 R 比较，计数不会增加。
有 j 种宝石和 s 颗石头时，最多需要进行 j × s 次比较。由于 j ≤ 52，处理 10^4 颗石头大约需要 5 × 10^5 次比较，在这里速度很快。随着种类数增加，开销也会增加，因为每颗石头都要重新搜索一次。
算法
- 将
count设为0。 - 对于每块石头，将它与
jewels中的每个字母进行比较。 - 遇到第一个相同的字母时，将
count加1，然后继续处理下一块石头。 - 返回
count。
def numJewelsInStones(jewels, stones):
count = 0
for stone in stones:
for jewel in jewels:
if stone == jewel:
count += 1
break # the kinds are distinct: no second match is possible
return count把宝石放进集合里
思路
对于给定的字母，“这个字母是不是宝石？”的答案不会改变，因此每种字母只计算一次：根据 jewels 中的字母构建一个集合。集合可以在常量时间内判断成员关系，因此每块石头只需查询一次，而不必扫描。
第一个示例中的集合是 {r, R}。遍历 rubyRRr 时，查询结果依次是是、否、否、否、是、是、是：共 4 块宝石。构建集合需要 j 步，遍历需要 s 步，因此总复杂度为 O(j + s)。在没有内置集合的语言中，可以用一个按字符编码索引的标志数组实现相同的功能。
算法
- 创建一个包含
jewels中每个字母的集合。 - 将
count设为0。 - 对于每块石头，如果集合中包含它，就将
count加1。 - 返回
count。
def numJewelsInStones(jewels, stones):
kinds = set(jewels)
count = 0
for stone in stones:
if stone in kinds:
count += 1
return count
易错点和边界情况
- 忽略大小写。将两个字符串都转换为小写后，
z就会匹配Z，第二个示例会返回3，而不是0。 - 统计不同种类的宝石，而不是宝石颗数。
rubyRRr包含两种宝石，但有四颗宝石；重复项也要计数。 - 在遍历宝石的循环中创建集合。每颗宝石都要花费
j步，这会让复杂度回到O(j × s)。 - 交换参数。集合必须存放
jewels，循环必须遍历stones。如果顺序反了，("a", "aaa")会返回1，而不是3。
常见问题3
宝石与石头的时间复杂度是多少？
使用集合时，时间复杂度为 O(j + s)：需要 j 步从 jewels 构建集合，并对每块 s 中的石头进行一次常数时间查找。每块石头都扫描一次 jewels，时间复杂度为 O(j × s)。
为什么在 Jewels and Stones 中使用哈希集合？
每块石头都会询问它的字母是不是宝石。哈希集合可以在常数时间内给出答案，而搜索 jewels 字符串所需的时间与它的长度成正比。你只需花费一次时间构建集合，之后处理每块石头时都能节省时间。
你能不用集合来解决它吗？
是的。这些字母都是英文字母，因此可以用一个由 128 个标志组成、按字符编码索引的数组作为集合，无需哈希。标记每个宝石字母，然后统计标志已设置的石头数量。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def numJewelsInStones(jewels, stones):
# 在这里编写代码测试 #1
测试 #2
参数
jewels = "rR" stones = "rubyRRr"
预期输出
4