题目描述

[EN | CN]

给定字符串 J 代表石头中宝石的类型,和字符串 S 代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,JS 中的所有字符都是字母。字母区分大小写,因此 "a" 和 "A" 是不同类型的石头。

示例 1:

1
2
输入: J = "aA", S = "aAAbbbb"
输出: 3

示例 2:

1
2
输入: J = "z", S = "ZZ"
输出: 0

注意:

  • SJ 最多含有 50`个字母。
  • J 中的字符不重复。

解法 1:Set

直接利用 set 来做即可。

假设石头数量为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,可以为常数空间(为了方便下面没有写成常数空间)。

实现与结果如下:

1
2
3
4
class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        j_set = set(J)
        return sum(s in j_set for s in S)
  • 执行用时:32 ms,在所有 Python3 提交中击败了 94.54% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 25.00% 的用户。