How do you solve Jewels and Stones on LeetCode?

Jewels and Stones (LeetCode #771) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashSet allows for faster lookups compared to checking each jewel individually.

What is the brute force solution for Jewels and Stones?

The brute force approach for Jewels and Stones is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we check each stone to see if it is a jewel. This is straightforward but can be inefficient as it requires checking each stone against all jewels. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Jewels and Stones?

Jewels and Stones uses the following concepts: Hash Table, String. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Jewels and Stones?

Always discuss your thought process and the trade-offs of different approaches. Be prepared to explain why you chose a particular data structure. Practice dry-running your code with sample inputs to ensure correctness.

What are common mistakes when solving Jewels and Stones?

Not using a data structure that allows for efficient lookups, leading to unnecessary time complexity. Confusing the case sensitivity of characters in jewels and stones.

#771

Jewels and Stones

Easy

Hash TableStringHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a HashSet to store jewels for O(1) average time complexity lookups. This reduces the overall time complexity significantly.

⚙️

Algorithm

5 steps

1Step 1: Create a HashSet from the jewels string for fast lookups.
2Step 2: Initialize a counter to zero to count jewels found in stones.
3Step 3: For each stone in the stones string, check if it exists in the HashSet of jewels.
4Step 4: If it exists, increment the counter.
5Step 5: Return the counter as the result.

solution.py7 lines

1def numJewelsInStones(jewels, stones):
2    jewel_set = set(jewels)
3    count = 0
4    for stone in stones:
5        if stone in jewel_set:
6            count += 1
7    return count

ℹ

Complexity note: The time complexity is O(n) because we create a HashSet from jewels (O(n)) and then check each stone (O(n)). The space complexity is O(n) due to the HashSet storing the jewels.

1Using a HashSet allows for faster lookups compared to checking each jewel individually.
2Understanding the difference between time complexity and space complexity is crucial for optimizing solutions.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.