Leetcode – Jewels and Stones Solution in Python

Spread the love

One of the classic programming challenges found on platforms like LeetCode involves problems that might seem simple on the surface but can be tackled using various methods, each with its unique complexities and trade-offs. The “Jewels and Stones” problem is one such question. It showcases the blend of string processing, data structures, and algorithmic thinking.

In this comprehensive article, we will dive deep into the problem, analyze its requirements, and explore multiple solutions in Python, ranging from the straightforward to the optimized.

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 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”.

Example:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Understanding the Problem

From the problem, we deduce:

  1. Only the stones that match the jewels exactly (including case sensitivity) should be counted.
  2. We need to find the count of occurrences of each jewel in the stone string.

Solution Approaches

Brute Force Approach

The most straightforward approach is to loop through each stone and check if it’s a jewel:

  1. Iterate over each stone.
  2. For each stone, iterate over each jewel to check if it matches.
  3. Count and return the total matches.

This approach, though functional, can be slow for large inputs.

Optimized Approach using Set Data Structure

Since we’re essentially checking for the presence of an item in a collection, we can leverage the set data structure in Python, which has an average time complexity of O(1) for the ‘in’ operation.

  1. Convert the jewel string into a set.
  2. Iterate over each stone and check if it’s in the set of jewels.
  3. Count and return the total matches.

Python Solutions

Brute Force Solution:

def numJewelsInStones(J: str, S: str) -> int:
    count = 0
    for stone in S:
        if stone in J:
            count += 1
    return count

# Example Usage
J = "aA"
S = "aAAbbbb"
print(numJewelsInStones(J, S))  # Expected output: 3

Optimized Solution:

def numJewelsInStones(J: str, S: str) -> int:
    jewels_set = set(J)
    return sum(1 for stone in S if stone in jewels_set)

# Example Usage
J = "aA"
S = "aAAbbbb"
print(numJewelsInStones(J, S))  # Expected output: 3

Complexity Analysis

Brute Force:

Time Complexity: O(m*n) where m is the length of string S and n is the length of string J.

Space Complexity: O(1) since we only use a constant amount of space beyond the input strings.

Optimized Solution:

Time Complexity: O(m + n). This accounts for converting the jewel string into a set and iterating over each stone.

Space Complexity: O(n) for storing the jewels in a set.

Conclusion

The “Jewels and Stones” problem exemplifies the recurring theme in programming challenges: there’s often more than one way to solve a problem. Although the brute force solution may be the first one to come to mind, thinking a bit more about the nature of the problem can lead to an optimized solution. The problem also illustrates the power of using the right data structures — in this case, the set — to simplify a problem and make the solution both cleaner and faster.

Leave a Reply