Leetcode 771. Jewels and Stones

Today we are going to solve Leetcode 771. Jewels and Stones

Photo by James Harrison on Unsplash

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.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

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

Example 2:

Input: jewels = "z", stones = "ZZ"
Output: 0

Constraints:

• 1 <= jewels.length, stones.length <= 50
• jewels and stones consist of only English letters.
• All the characters of jewels are unique.

Solution

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.

sksaikia/LeetCode