Today we are going to solve Leetcode 771. Jewels and Stones
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.
Letters are case sensitive, so
"a" is considered a different type of stone from
Input: jewels = "aA", stones = "aAAbbbb"
Input: jewels = "z", stones = "ZZ"
1 <= jewels.length, stones.length <= 50
stonesconsist of only English letters.
- All the characters of
As we can see from the problem statement, this is a problem for finding the occurrence of one character in another string. Here we are asked to find the number of stones that are jewels. We are given the Jewels and Stones. Therefore, what we can do is that we can add the jewels in an
HashSet and count the number of stones that are also jewels. We are using
HashSet because with
HashSet , we can find an entry in
O(1) time. The code can be found below.
Time Complexity: O(n), n is the length of the stones string
Space Complexity: O(m), m is the length of the jewels string
The code can be found in this repository.