[LEET CODE] 771. Jewels and Stones

# Problem

You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels. Letters are case sensitive, so "a" is considered a different type of stone from "A". Constraints: 1 <= jewels.length, stones.length <= 50 jewels and stones consist of only English letters. All the characters of jewels are unique.

 

# My Answer

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        result =0
        for j in jewels:
            for s in stones:
                if s==j:
                    result+=1
        return result

 

# Solution 1 - 해시 테이블을 이용한 풀이

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        freqs = {}
        count = 0

        # 돌(S)의 빈도 수 계산
        for char in S:
            if char not in freqs:
                freqs[char] = 1
            else:
                freqs[char] += 1

        # 보석(J)의 빈도 수 합산
        for char in J:
            if char in freqs:
                count += freqs[char]

        return count

먼저 stone의 수를 count 후 보석 수 반환

 

# Solution 2 - defaultdict를 이용한 비교 생략

import collections


class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        freqs = collections.defaultdict(int)
        count = 0

        # 비교 없이 돌(S) 빈도 수 계산
        for char in S:
            freqs[char] += 1

        # 비교 없이 보석(J) 빈도 수 합산
        for char in J:
            count += freqs[char]

        return count

defaultdict에 존재하지 않는 키는 자동으로 디폴트 생성

 

# Solution 3 - Counter로 계산 생략

import collections


class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        freqs = collections.Counter(S)  # 돌(S) 빈도 수 계산
        count = 0

        # 비교 없이 보석(J) 빈도 수 합산
        for char in J:
            count += freqs[char]

        return count

Counter를 사용하여 개수 자동 계산

 

# Solution 4 - 파이썬다운 방식

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        return sum(s in J for s in S)

리스트 컴프리헨션

[s for s in S]

[ 'a', 'A', 'A', 'b', 'b', 'b', 'b' ]

 

[s in J for s in S]

[ True, True, True, False, False, False, False ]

 

sum을 하면 True의 개수는 구할 수 있다