Question
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".
Example1:
Input: J = "aA", S = "aAAbbbb"
Output: 3
Example2:
Input: J = "z", S = "ZZ"
Output: 0
Thought(思路)
It is easy to do. I will talk about thought and data structure.(思路很简单，大致说一下，主要说一下可能涉及到的数据结构。)
J include unrepeated elements. Let us loop J and check whether everyone of J is included S and sum the counts.(J是不会重复的，循环J中所有元素，看是否在S中，在，就统计个数。)
Data structure
Array, Hashtable/Hashmap, Tree(Linklist).
In python3, Accessing set is faster than accessing list.(在python3中，访问集合比访问列表速度快）
How to use map().
map function takes an arbitrary function and applies it over the elements of an iterable. An iterable, loosely speaking, is anything which allows you to loop through its elements.
Consider this example,
>>> round(2.3)
2
>>> round(4.9)
5
>>> rounded = map(round, [2.3, 4.9])
>>> list(rounded)
[2, 5]
There are two main components to this example:
- the round function
- the iterable i.e., list [2.3, 4.9]
Let’s say you have this list of hundred numbers that you want to round off. Of course, you are not going to write hundred round statements. One of the many ways to achieve this [in Python] is to use map.
You can provide map with the function as argument, and the list of elements on which it has to be applied. The result is a generator expression. The last step retrieves the results from the generator.
Now, let’s look at the code below:
a, b = map(int, input().split())
Here’s a breakdown:
In [0]: input().split()
12 13
Out [0]: ['12', '13']
That is, take an input, split it and create a list, then convert them into an integer by mapping the function int, finally save the results in variables a, b.
That’s one way you can take multiple inputs on the same line.
source from: https://www.quora.com/What-does-a-map-function-do-in-Python-3
Code
#the First solution
class Solution:
def numJewelsInStones(self, J, S):
"""
:type J: str
:type S: str
:rtype: int
"""
j = set(list(J))
s = list(S)
count = 0
for stone in s:
if stone in j:
count += 1
return count
#the Second
class solution:
def numJewelsInStones(self,J,S):
return sum(s in J for s in S)
#the Third
class solution:
def numJewelsInStones(self, J, S):
return sum(map(J.count, S))
#the Fourth
class solution:
def numJewelsInStones(self, J, S):
return sum(map(S.count, J))
Complexity
Time complexity: (s is length of S,j is length of J)(为字符串S的长度，j为字符串J的长度)
Space complexity:
