DEV Community

loading...
Cover image for Jewels 💎 and Stones ⛰

Jewels 💎 and Stones ⛰

snappydevlpr profile image Austin ・2 min read

Here is a rocking problem that shows how to deal with arrays.

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Brute Force 👊

Looking at a brute force method I would use a double for loop which would increase my BigO notation to the length of S multiplied by length J. Here I would have to iterate through the stones multiple times for each jewel I am referencing.

An Optimal Solution

Looking at this problem what comes to mind is using some sort of hashmap or set. Today I'm going to be switching it up and using C++. In C++ there is a structure you can take advantage of known as an unordered_set. This will let us store unique values in a container based on a key 🔑. Looking at this problem here I can make the jewels my unordered set and search them quickly. This will also allow me to decrease my time complexity to the length of S plus by length J.

There are a couple of other ways to solve this problem so put your solution down below! Thanks for reading, like and follow for more! 🙃

Discussion

pic
Editor guide