Skip to content

Latest commit

 

History

History
65 lines (39 loc) · 2.33 KB

063.md

File metadata and controls

65 lines (39 loc) · 2.33 KB

771. Jewels and Stones

Difficulty: 🟢 Easy

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

Examples:

Example 1:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

Example 2:

Input: jewels = "z", stones = "ZZ"
Output: 0

Constraints:

  • 1 <= jewels.length, stones.length <= 50
  • jewels and stones consist of only English letters.
  • All the characters of jewels are unique.

Solutions

O(n) solution

Python 3

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        items = set([jewel for jewel in jewels])
        return sum([1 for stone in stones if stone in items])

The given solution provides a straightforward approach to solving the problem.

Here is an overview of the solution:

  1. Create a set called items to store the unique types of stones that are jewels. Iterate through each character in the jewels string and add it to the set.
  2. Use a list comprehension to iterate through each character in the stones string. Check if the character is present in the items set. If it is, increment a counter by 1.
  3. Return the counter, which represents the number of stones that are also jewels.

Complexity Analysis

The time complexity for this solution is O(len(jewels) + len(stones)), as we iterate through the jewels string to create the items set and iterate through the stones string to count the jewels.

The space complexity is O(len(jewels)) because we create a set to store the unique types of jewels.

Summary

The given solution provides a straightforward approach to count the number of stones that are also jewels. It creates a set of unique jewels and iterates through the stones, incrementing a counter for each stone that is present in the set. The solution runs in linear time and requires additional space to store the set of jewels.

NB: If you want to get community points please suggest solutions in other languages as merge requests.