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! 🙃
Top comments (0)