Leetcode 771. Jewels and Stones

Problem Explanation

The problem gives us two strings of type String(J and S). The string J represents types of stones that are Jewels while the string S represents the stones you have. Every character in J and S are distinct letters and case sensitive. Therefore, lowercase 'a' and uppercase 'A' are considered two different types of stones. The task is to determine how many of the stones we have are also jewels.

Example

Using the following example:

1
2
3Input: J = "aA", S = "aAAbbbb"
4Output: 3

The string J has two types of jewels 'a' and 'A'. The string S has 4 'b's, 2 'A's, and 1 'a'. The only stone types in S that we have that are also in J are stones of type 'A' and 'a'. Hence the output is 3.

Solution Approach

Our approach to solve this problem is by iterating through each character in our string S, and if the character appears in our string J, we increment our counter. The counter at the end of this operation will represent the total number of jewels we have in our string S. One effective way to achieve this is by using an Unordered Set. An Unordered Set data structure can quickly check if a particular element exists in it or not.

Python Solution

1
2python
3class Solution:
4    def numJewelsInStones(self, jewels: str, stones: str) -> int:
5        jewelsSet = set(jewels)
6        jewelsCount = 0
7        for stone in stones:
8            # check if the stone is a jewel
9            if stone in jewelsSet:
10                jewelsCount += 1
11        return jewelsCount

Java Solution

1
2java
3class Solution {
4    public int numJewelsInStones(String jewels, String stones) {
5        Set<Character> jewelsSet = new HashSet<>();
6        for (char j : jewels.toCharArray()) {
7            // each character in J is added to hashset
8            jewelsSet.add(j);
9        }
10        int count = 0;
11        for (char s : stones.toCharArray()) {
12            // if stone is found in hashset, increment count
13            if (jewelsSet.contains(s)) {
14                count++;
15            }
16        }
17        return count;
18    }
19}

Javascript Solution

1
2javascript
3var numJewelsInStones = function(jewels, stones) {
4    let setJ = new Set(jewels);
5    let count = 0;
6    for(let s of stones)
7        // if stone is found in set, increment count
8        if(setJ.has(s))
9            count += 1;
10    return count;
11};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int numJewelsInStones(string J, string S) {
6        unordered_set<char> jewelsSet(J.begin(), J.end());
7        int jewelsCount = 0;
8        for (char stone : S) {
9            // if stone is found in set, increment count
10            if (jewelsSet.count(stone))
11                jewelsCount++;
12        }
13        return jewelsCount;
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    public int NumJewelsInStones(string jewels, string stones) {
5        var jewelsSet = new HashSet<char>(jewels);
6        int count = 0;
7        foreach (char stone in stones) {
8            // if stone is found in hashset, increment count
9            if(jewelsSet.Contains(stone))
10                count++;
11        }
12        return count;
13    }
14}

This approach has a space complexity of O(J) - where J is the number of jewels; and a time complexity of O(S) - where S is the number of stones.# Ruby Solution

1
2ruby
3def num_jewels_in_stones(jewels, stones)
4  jewels_set = jewels.each_char.to_set()
5  count = 0
6  stones.each_char do |stone|
7    if jewels_set.include?(stone)
8      count += 1
9    end
10  end
11  return count
12end

Swift Solution

1
2swift
3func numJewelsInStones(_ jewels: String, _ stones: String) -> Int {
4    let jewelsSet = Set(jewels)
5    var count = 0
6    for stone in stones {
7        if jewelsSet.contains(stone) {
8            count += 1
9        }
10    }
11    return count
12}

Scala Solution

1
2scala
3def numJewelsInStones(jewels: String, stones: String): Int = {
4  val jewelsSet = jewels.toSet
5  var count = 0
6  for(stone <- stones) {
7    if(jewelsSet.contains(stone)) {
8      count += 1
9    }
10  }
11  count
12}

Kotlin Solution

1
2kotlin
3fun numJewelsInStones(jewels: String, stones: String): Int {
4    val jewelsSet = jewels.toHashSet()
5    var count = 0
6    for(stone in stones) {
7        if(jewelsSet.contains(stone)) {
8            count += 1
9        }
10    }
11    return count
12}

PHP Solution

1
2php
3function numJewelsInStones(string $jewels, string $stones): int {
4    $jewelsSet = str_split($jewels);
5    $count = 0;
6    for($i = 0; $i < strlen($stones); $i++) {
7        if(in_array($stones[$i], $jewelsSet)) {
8            $count++;
9        }
10    }
11    return $count;
12}

Golang Solution

1
2golang
3func numJewelsInStones(jewels string, stones string) int {
4    jewelsSet := make(map[rune]bool)
5    for _, j := range jewels {
6        jewelsSet[j] = true
7    }
8    count := 0
9    for _, s := range stones {
10        if jewelsSet[s] {
11            count++
12        }
13    }
14    return count
15}

Every solution uses the same logic: walk through the list of stones and, if a stone is a jewel, increase the counter. The key part is the use of a set to hold the jewels, which allows for O(1) lookup time.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫