771. 宝石与石头

题目

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

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

示例 1:

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

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

注意:

S 和 J 最多含有50个字母。 J 中的字符不重复。

解题思路

思路：哈希表

暴力解

这里，我们可能首先想到的是使用两层遍历，找到手中拥有的石头究竟有多少是宝石。具体做法大致如下：

先遍历拥有的石头，也就是字符串 S； 对于 S 中的每个字符，遍历一次字符串 J，也就是宝石的类型； 如果 S 中的字符与字符串 J 的某个宝石类型相同，则将其计数。

具体的代码如下：

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        # 统计计数
        count = 0
		# 遍历字符串 S
        for s in S:
            # 判断字符是否存在于 J 中
            # 这里 in 在字符串中查找时间复杂度为 O(n)
            if s in J:
                # 存在则进行计数
                count += 1

        return count

复杂度分析

时间复杂度： O ( m n ) O(mn) O(mn)，其中 m m m 为字符串 S 的长度， n n n 为字符串 J 的长度。 空间复杂的： O ( 1 ) O(1) O(1)，只使用了常数的额外空间。

哈希表

上面的方法中，需要两层遍历去查找宝石的个数。对于字符串 S 中的每个字符，每次都需要遍历 J 去查找是否存在。

这里我们可以使用哈希集合去存储 J 中的每个字符，那么遍历字符串 S，只要判断 S 的每个字符是否存在于集合中。若存在，则为宝石，进行计数；否则不处理。

具体的代码实现如下：

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        # 用集合存储 J 中的字符
        jewel_set = set()
        for j in J:
            jewel_set.add(j)

        count = 0
		# 遍历 S
        for s in S:
            # 判断是否存在于集合中
            if s in jewel_set:
                count += 1

        return count

复杂度分析

时间复杂度： O ( m + n ) O(m+n) O(m+n)， m m m 为 S 字符串长度， n n n 为 J 字符串长度。遍历 J，将字符存储到集合中，时间复杂度为 O ( n ) O(n) O(n)；遍历 S，每个字符查找时间为 O ( 1 ) O(1) O(1)，这里时间复杂度为 O ( m ) O(m) O(m)，所以总时间复杂度为 O ( m + n ) O(m+n) O(m+n)。 空间复杂度： O ( n ) O(n) O(n)，这里为哈希集合的开销。

如有错误，烦请指出，欢迎指点交流。