This is an easy question, it just takes me less than 3 min to finish it. But I still want to write down the details because we can learn how to write more pythonic way from it.


How much times for each char of string J occurs in string S.

For each char in string J, we only need one for loop to sum each char’s frequency in String S.

And we use count function to count the frequency of each char’s occurrence.

So, we have the following code:

class Solution:
    def numJewelsInStones(self, J, S):
        :type J: str
        :type S: str
        :rtype: int
        J = list(J)
        counts = 0
        for c in J:
            counts += S.count(c)
        return counts

What if we do note use the python function count, the burst way is:

J = list(J)
counts = 0
for c in S:
    if c in C: 
        count += 1
return counts

To be brief:

return sum(if c in J for c in S)


For hash set, it takes $O(1)$ to check if it contains an element. So we can use set to reduce the time space of finding the number. Then we have the time complexity $O(M+N)$ in this case.

Here are the code:

J_set = set(J)
return sum(if c in J_set (for c in S))

The optional way is using map, the logic is the same with first solution:

return sum(map(J.count, S))

The map() function executes a specified function for each item in a iterable. [wiki]

So why using map is faster than the first solution? The point is we have to understand the implementation of map.


The runtime for those four solution:

way Runtime
map 52 ms
set 52 ms
brute 64ms
count 80ms


Further question

What is the difference between list and set in python? When should we use the set structure? What is the implementation of map in python?