Jewels And Stones - Leetcode Solution

Problem description:

You're given a string J representing the types of stones that are jewels, and a string 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:

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

Solution:

The problem can be solved by counting the number of jewels in the stones. For each stone, we can check if it's a jewel and increment the counter if it is. The time complexity of this algorithm is O(n), where n is the number of stones.

Algorithm:

1. Initialize a counter variable to 0.
2. Loop through each stone in S. a. Check if the stone is a jewel by searching for it in J. b. If the stone is a jewel, increment the counter.
3. Return the counter value.

Python code snippet:

def numJewelsInStones(self, J: str, S: str) -> int:
    jewels = set(J)
    count = 0
    for stone in S:
        if stone in jewels:
            count += 1
    return count

Explanation:

In the above code snippet, we first create a set of jewels by converting the string J to a set. This way, we can search for jewels in constant time using the in keyword.

We then initialize the counter variable to zero and loop through each stone in S. For each stone, we check if it is a jewel by searching for it in the jewels set. If the stone is a jewel, we increment the counter.

Finally, we return the counter value, which gives us the number of stones that are also jewels.

This algorithm has a time complexity of O(n), where n is the number of stones, since we perform a constant-time search for each stone in the jewels set.

1