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 <= 50jewels and stones consist of only English letters.jewels are unique.This approach leverages a Set (or a HashSet in some languages) for quickly determining if a stone is a jewel. The idea is to store all the jewel types in a set, then iterate through each stone, checking if the stone is in the set. If it is, we increment our count of jewels found.
In the C implementation, we define a helper function isJewel that checks if a character is a jewel by iterating through the jewel string. For each stone, we call this function and increment our count accordingly. This is not the most optimized as it involves iterating through the jewels for each stone.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), where n is the number of stones and m is the number of jewels. Space Complexity: O(1), since no extra space is used other than for the input strings.
This approach uses an array to quickly map each character to an index, allowing us to count frequencies of jewels in the stones. Since the input is restricted to English letters, a fixed-size array of 52 (for each upper and lower case letter) is adequate.
This C solution uses an array of size 52 to represent each letter as a potential jewel. This approach handles both uppercase and lowercase characters distinctly, using ASCII arithmetic to map letters to indices.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the length of jewels and m is the length of stones. Space Complexity: O(1), using a fixed-size array for character mapping.
| Approach | Complexity |
|---|---|
| Using a Set for Fast Lookup | Time Complexity: O(n * m), where n is the number of stones and m is the number of jewels. Space Complexity: O(1), since no extra space is used other than for the input strings. |
| Using Array for Character Indexing | Time Complexity: O(n + m), where n is the length of jewels and m is the length of stones. Space Complexity: O(1), using a fixed-size array for character mapping. |
Jewels and Stones - Leetcode 771 - Hashmaps & Sets (Python) • Greg Hogg • 14,426 views views
Watch 9 more video solutions →Practice Jewels and Stones with our built-in code editor and test cases.
Practice on FleetCode