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:
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?