# LeetCode Easy 771. Jewels and Stones

tags: leetcode

問題

• Explore
• Problems

アイデア

Jというジュエリーである宝石の種類を表現する文字列とSという持っている宝石を表現する文字列が与えられます．持っている宝石のうち，ジュエリーであるものの個数を返せという問題です．

解法

• setでJの宝石を保管します．
• Sの宝石がこの中にあれば答えを1つ大きくします．

計算量

J，Sの大きさがそれぞれ$N$，$M$だとします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(M)$

Python

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        stones = set()
        count = 0
        for stone in J:
            stones.add(stone)
        for stone in S:
            if stone in stones:
                count += 1
        return count