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.(思路很簡單，大致說一下蓝翰，主要說一下可能涉及到的數(shù)據(jù)結(jié)構(gòu)害碾。)
J include unrepeated elements. Let us loop J and check whether everyone of J is included S and sum the counts.(J是不會重復(fù)的，循環(huán)J中所有元素春锋，看是否在S中累贤，在舱权，就統(tǒng)計(jì)個數(shù)矗晃。)
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:
