Jewels and Stones (via Leetcode)¶

Date published: 2020-03-25

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops

Problem Statement¶

You're given strings J representing the types of stones that are jewels, and 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 that 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".

Test Cases¶

Test case #1:

• Input: J = "aA", S = "aAAbbbb"
• Output: 3
• Reasonsing: The first 3 characters in S are characters that are in J

Test case #2:

• Input: J = "z", S = "ZZ"
• Output: 0
• Reasonsing: There are no instances of z in S

In [ ]:

# assert count_jewels_in_stones(J = "aA", S = "aAAbbbb") == 3
# assert count_jewels_in_stones(J = "z", S = "ZZ") == 0

# assert count_jewels_in_stones(J = "aA", S = "aAAbbbb") == 3 # assert count_jewels_in_stones(J = "z", S = "ZZ") == 0

Pseudocode¶

This code uses minimal storage - a low space complexity - of just O(1) since the 1 represents the space of the variable count_jewels_in_collection.

However, this code has a high time complexity because for every element in J, I must search all elements in S. If we use the letter n to assign the length of items in J and m to assign the length of items in S, then the time complexity is O(mn).

In [1]:

# create function to take in J and S

    # create a variable - a counter - to count the number of jewels found in the stones collection

    # iterate over each element in J
        # iterate over each item in S
            #  if element is equal to item
                # increment the counter by 1
    # return counter

# create function to take in J and S # create a variable - a counter - to count the number of jewels found in the stones collection # iterate over each element in J # iterate over each item in S # if element is equal to item # increment the counter by 1 # return counter

Code¶

In [3]:

def count_jewels_in_stones(J, S):
    count_jewels_in_collection = 0

    for element in J:
        for item in S:
            if element == item:
                count_jewels_in_collection += 1
    return count_jewels_in_collection

def count_jewels_in_stones(J, S): count_jewels_in_collection = 0 for element in J: for item in S: if element == item: count_jewels_in_collection += 1 return count_jewels_in_collection

Let's run the assert statements below to verify the function passes these test cases.

In [4]:

assert count_jewels_in_stones(J = "aA", S = "aAAbbbb") == 3
assert count_jewels_in_stones(J = "z", S = "ZZ") == 0

assert count_jewels_in_stones(J = "aA", S = "aAAbbbb") == 3 assert count_jewels_in_stones(J = "z", S = "ZZ") == 0

Pseudocode #2 Solution¶

The above answer had high time complexity and low space complexity. I can design an alternative solution as a tradeoff with low time complexity and high space complexity.

I will use a Python set covered in detail here in the official documentation.

In the code below, the set represents an O(n) space complexity and the variable is an O(1) space complexity.

I iterate over each element in S so my code has an O(m) time complexity.

In [6]:

# assign each letter in J to be a value in a Python set

# store a variable as a counter of occurences of J in S

# iterate over each element in S
    # if element is in Python set of S characters
        # append 1 to counter

# assign each letter in J to be a value in a Python set # store a variable as a counter of occurences of J in S # iterate over each element in S # if element is in Python set of S characters # append 1 to counter

Code #2 Solution¶

In [10]:

def count_jewels_in_stones2(J, S):
    s_set = set(J)
    count_jewels_in_collection = 0

    for item in S:
        if item in s_set:
            count_jewels_in_collection += 1
    return count_jewels_in_collection

def count_jewels_in_stones2(J, S): s_set = set(J) count_jewels_in_collection = 0 for item in S: if item in s_set: count_jewels_in_collection += 1 return count_jewels_in_collection

Let's run the assert statements below to verify this new function passes these test cases.

In [11]:

assert count_jewels_in_stones2(J = "aA", S = "aAAbbbb") == 3
assert count_jewels_in_stones2(J = "z", S = "ZZ") == 0

assert count_jewels_in_stones2(J = "aA", S = "aAAbbbb") == 3 assert count_jewels_in_stones2(J = "z", S = "ZZ") == 0