771. Jewels and Stones

Easy

Problem:

J represents jewels, and S represents the stones you have. How many jewels are in S? Uppercase and lowercase letters are distinguished. (=Letters are case sensitive)

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

https://leetcode.com/problems/jewels-and-stones

Solution:

Hash Table

After counting each of the stones in S, you can solve it by summing the counts of each element in J used as a key.

def numJewelsInStones(self, jewels: str, stones: str) -> int:
    freqs = {}
    count = 0
    
    # Calculate the frequency of S
    for char in stones:
        if char not in freqs:
            freqs[char] = 1
        else:
            freqs[char] += 1
    
    # Calculate the frequency of J
    for char in jewels:
        if char in freqs:
            count += freqs[char]
            
    return count

Defaultdict

import collections

def numJewelsInStones(self, jewels: str, stones: str) -> int:
    freqs = collections.defaultdict(int)
    count = 0
    
    for char in stones:
        freqs[char] += 1
    
    for char in jewels:
        count += freqs[char]
    
    return freqs

Counter

Counter does not raise a KeyError for non-existent keys; instead, it returns 0. Therefore, just like with defaultdict, there's no need to handle exceptions for errors.

import collections

def numJewelsInStones(self, jewels: str, stones: str) -> int:
    freqs = collections.Counter(stones) 
    count = 0
    
    for char in jewels:
        count += freqs[char]
    
    return count

Pythonic way

List Comprehension

• [s for s in stones]: ['a', 'A', 'A', 'b', 'b', 'b', 'b']

• [s in jewels for s in stones]: [True, True, True, False, False, False, False]

def numJewelsInStones(self, jewels: str, stones: str) -> int:
    return sum(s in jewels for s in stones) # sum([s in J for s in S])