deepSWE.io

Jewels and Stones

Hashing

10 min

Problem Statement

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.

Example

Example 1:

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

Output: 3

Solution (Hash Set)

We can use a hash set to store the types of jewels. This allows for O(1) time complexity when checking if a stone is a jewel.

Algorithm Steps

Create a hash set and add all characters from the `jewels` string to it.
Initialize a `count` variable to 0.
Iterate through the `stones` string.
For each stone, check if it exists in the jewels set.
If it does, increment the `count`.
After iterating through all stones, return `count`.

Jewels:

Stones:

Jewels Set

Stones

Count

Created a set of jewels: {a, A}

Jewels and Stones Solution


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