LeetCode 771 · Hashing

Jewels and Stones, explained with a picture

Sorting jewels from a bag of stones.

Hashing
▶ Watch it step by step

The problem

Given jewel types and a bag of stones, count how many stones are jewels. Letters are case-sensitive.

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

Picture it

Picture sorting a miner’s bag. Put the jewel types in a set, then check each stone against the set in one step.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Set membership per stone. O(j + s).

Python solution

def num_jewels(jewels, stones):
    kinds = set(jewels)
    count = 0
    for s in stones:
        if s in kinds:
            count += 1
    return count

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.