Q771 Jewels and Stones

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note: S and J will consist of letters and have length at most 50. The characters in J are distinct.

解题思路：

J 用字典或者集合（Python 中判断集合中元素是否存在也是 O(1) 的时间）存储起来，然后遍历 S 中的每一个字符，判断字符是否也出现在 J 中。

时间复杂度 O(M+N)

Python 实现：

class Solution:
    # AC: O(len(J) + len(S))
    def numJewelsInStones(self, J, S):
        """
        :type J: str
        :type S: str
        :rtype: int
        """
        J = set(J) # Python 中 set 判断元素是否存在的时间复杂度为 O(1)
        return sum(ch in J for ch in S) 

a = "aA"
b = "aAAbbbb"
print(Solution().numJewelsInStones(a, b))  # 3