771. Jewels and Stones
Problem Description
In this problem, we are given two strings, jewels
and stones
. The jewels
string represents the types of stones that are considered to be jewels. Each character in the jewels
string is a unique jewel type. The stones
string contains the stones that we have, and each character represents a type of stone. Our task is to count how many stones we have that are also jewels. It is important to note that the identification of jewels is case sensitive, meaning a
and A
would be treated as different types of stones.
Intuition
The solution approach involves using a set data structure in Python, which contains only unique items and allows for fast membership testing. By converting the jewels
string into a set, we can quickly check if a stone (character in stones
string) is a jewel by seeing if it exists in the set.
Here is the intuition behind the steps:
- Convert the
jewels
string into a set. This is important to remove any duplicate characters, which can occur in the input, and to allow for O(1) (constant time) look-ups. - Iterate through each character in the
stones
string. For every stone, we will check if it's also a jewel. - We check if a stone is a jewel by determining if that stone (character) is present in the
jewels
set. - Count the number of stones that are jewels. This is done by summing the number of True values yielded by the expression
c in s
for each stonec
in thestones
string, wheres
is the set of jewels. - Return the count as the final answer.
The reasoning behind this approach is centered on set theoryāby comparing elements of one set (our stones) to another (our jewels), we're looking for the intersectionāthe items that are common to both. The use of a set data structure simplifies this search, making the algorithm efficient and concise.
Solution Approach
The implementation of the solution relies on several concepts and data structures, which optimize the process of identifying jewels within the stones. Let's dive into the approach based on the reference solution:
-
Set Data Structure: The solution begins with creating a set
s
from thejewels
string. Sets are an appropriate choice for two main reasons: they inherently prevent duplicate elements and provide constant time complexity (O(1)
) for membership checking. This is crucial because it prevents the algorithm's performance from degrading, even with a large number of jewel types.s = set(jewels)
-
For Loop and Membership Testing: We iterate through each character
c
in the stringstones
, which allows us to examine each stone we possess.for c in stones:
-
Boolean Expression in Sum: For every stone represented by character
c
, we test if it is in the sets
(the jewels). The expressionc in s
evaluates to a boolean (True
ifc
is a jewel,False
if not).c in s
-
Sum to Count Trues: The sum function in Python conveniently treats
True
as1
andFalse
as0
. Thus, when we sum up the boolean expression results, we effectively count how many timesc in s
evaluates toTrue
, which corresponds to the number of stones that are jewels.sum(c in s for c in stones)
-
Return the Result: The result of the sum operation is the final answer, which is the number of stones that are also jewels.
Combining these steps in a single expression leads to a compact and efficient solution. The solution's elegance lies in its use of Python's set and iteration mechanisms to directly tie together the question (is this a jewel?) with the answer (how many jewels?).
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
s = set(jewels)
return sum(c in s for c in stones)
This Python code snippet achieves our goal using advanced concepts in an easy-to-understand and concise way.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a simple example to illustrate the solution approach. Suppose we have the following inputs:
jewels
:"aA"
stones
:"aAAbbbb"
As per the problem statement, each character in the jewels
string is a unique jewel type, and they are case-sensitive. So in this case, we have two types of jewels: 'a'
and 'A'
. We have to find out how many of the stones are actual jewels.
Following the steps from the solution approach:
-
Convert the
jewels
string into a set. Thus, we create a set of jewelss
:s = set('aA') # The set will contain {'a', 'A'}
-
Iterate through each character in the
stones
string using a for loop:for c in "aAAbbbb":
-
For each character
c
instones
, check if it is present in the set of jewelss
. We'll do this using the expressionc in s
, which returnsTrue
ifc
is a jewel, otherwiseFalse
:'a' in s # True 'A' in s # True 'A' in s # True 'b' in s # False 'b' in s # False 'b' in s # False 'b' in s # False
-
We evaluate the expression
c in s
inside asum()
function to add up theTrue
values (which are counted as1
):sum(c in s for c in "aAAbbbb") # This will equal 3
-
The result of the sum expression (3 in this case) is the number of stones that are also jewels, which is what we return as the answer.
Following this process, we were able to determine that out of the stones we possess ("aAAbbbb"
), three of them are jewels ("aAA"
).
Solution Implementation
1class Solution:
2 def numJewelsInStones(self, jewels: str, stones: str) -> int:
3 # Convert the string jewels into a set for faster lookup
4 jewel_set = set(jewels)
5
6 # Count how many characters in stones are also in jewel_set
7 # The expression (char in jewel_set) returns True if the char is a jewel,
8 # and False otherwise. sum() treats True as 1 and False as 0.
9 jewel_count = sum(char in jewel_set for char in stones)
10
11 # Return the total count of jewels in the stones
12 return jewel_count
13
1class Solution {
2 public int numJewelsInStones(String jewels, String stones) {
3 // An array to keep track of all the ASCII characters.
4 // The size is 128 as there are 128 ASCII characters.
5 int[] asciiMap = new int[128];
6
7 // Iterate over the characters in 'jewels' and mark them in the asciiMap.
8 for (char jewel : jewels.toCharArray()) {
9 asciiMap[jewel] = 1;
10 }
11
12 // 'totalJewels' holds the count of jewels found in 'stones'.
13 int totalJewels = 0;
14
15 // Iterate over the characters in 'stones'.
16 for (char stone : stones.toCharArray()) {
17 // If a character in 'stones' is marked as 1 in asciiMap,
18 // it is a jewel, so we increment the totalJewels count.
19 totalJewels += asciiMap[stone];
20 }
21
22 // Return the total count of jewels found in 'stones'.
23 return totalJewels;
24 }
25}
26
1class Solution {
2public:
3 int numJewelsInStones(string jewels, string stones) {
4 // Array to store whether a character is considered a jewel.
5 // The ASCII value of the character will serve as the index.
6 int jewelFlags[128] = {0};
7
8 // Mark the jewels in the 'jewelFlags' array.
9 for (char jewelChar : jewels) {
10 jewelFlags[jewelChar] = 1;
11 }
12
13 // Count variable to keep track of the number of jewels found in 'stones'.
14 int jewelCount = 0;
15
16 // Iterate through each character in 'stones' to see if it's marked as a jewel.
17 for (char stoneChar : stones) {
18 // Increase count if current character is marked as a jewel.
19 jewelCount += jewelFlags[stoneChar];
20 }
21
22 // Return the total count of jewels present in 'stones'.
23 return jewelCount;
24 }
25};
26
1/**
2 * Counts how many stones you have that are also jewels.
3 * @param {string} jewels - The string representing the types of jewels.
4 * @param {string} stones - The string representing the stones you have.
5 * @returns {number} The number of stones that are also jewels.
6 */
7function numJewelsInStones(jewels: string, stones: string): number {
8 // Create a Set to store unique jewel characters for quick lookup
9 const jewelSet = new Set<string>([...jewels]);
10
11 // Initialize a count variable to keep track of jewels found in stones
12 let count = 0;
13
14 // Iterate over the stones string to check if a stone is also a jewel
15 for (const stone of stones) {
16 // If the current stone is in the jewel set, increment the count
17 if (jewelSet.has(stone)) {
18 count++;
19 }
20 }
21
22 // Return the total count of jewels found in stones
23 return count;
24}
25
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n + m)
where n
is the length of the jewels
string and m
is the length of the stones
string. The creation of the set s
from the jewels
string takes O(n)
time. Then, we iterate over each character c
in stones
, which takes O(m)
time, to check whether it is in the set s
. Since set lookup is O(1)
on average, the time for the sum operation is also O(m)
.
Space Complexity
The space complexity is O(n)
, where n
is the length of the jewels
string. This is because we create a set s
to store the distinct characters in jewels
. There is no additional significant space used as we only store a single set.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!