【LeetCode】【HashTable】jewels and stones

时间：2020-06-30 23:56:15 收藏：0 阅读：83

题目：

您得到的字符串J代表宝石的宝石类型，而S代表您拥有的宝石。 S中的每个字符都是您拥有的一块石头。您想知道您拥有多少宝石也是珠宝。

J中的字母是不同的，并且J和S中的所有字符都是字母。字母区分大小写，因此“ a”被认为与“ 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.

【解法一】

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        n = 0
        for i in J:
            for j in S:
                if i == j:
                    n += 1
        return n

Runtime: 44 ms, faster than 19.01% of Python3 online submissions for Jewels and Stones.

Memory Usage: 13.8 MB, less than 57.27% of Python3 online submissions for Jewels and Stones.

【解法二】

def numJewelsInStones(self, J, S):
    return sum(map(J.count, S))

def numJewelsInStones(self, J, S):
    return sum(map(S.count, J))

#Runtime: 52 ms, faster than 9.83% of Python3 online submissions for Jewels and Stones.

#Memory Usage: 13.9 MB, less than 40.78% of Python3 online submissions for Jewels and Stones，

return sum(s in J for s inS)
#is equal to:
int res = 0
for s in S:
    if s in setJ:
       res += 1
return res

Runtime: 44 ms, faster than 19.01% of Python3 online submissions for Jewels and Stones.

Memory Usage: 14 MB, less than 17.51% of Python3 online submissions for Jewels and Stones.

差别：一个有[ ]一个没有

def numJewelsInStones(self, J, S):
    return sum([s in J for s in S])

Runtime: 20 ms, faster than 98.42% of Python3 online submissions for Jewels and Stones.

Memory Usage: 13.9 MB, less than 35.01% of Python3 online submissions for Jewels and Stones.

【解法】

用hash table的思想。

    def numJewelsInStones(self, J, S):
        charToFreqS = {}  # Map character to its frequency in S.
        numJewels = 0  # Total number of jewels.
        
        for ch in S:
            if ch not in charToFreqS:
                charToFreqS[ch] = 1
            else:
                charToFreqS[ch] += 1
        
        for ch in J:
            if ch in charToFreqS:
                numJewels += charToFreqS[ch]
                
        return numJewels

Runtime: 44 ms, faster than 19.01% of Python3 online submissions for Jewels and Stones.

Memory Usage: 13.8 MB, less than 46.96% of Python3 online submissions for Jewels and Stones.

原文：https://www.cnblogs.com/jialinliu/p/13216670.html