[Algorithm] 771. Jewels and Stones

Description

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

Key Requirements of the Problem

Find the characters in the jewels string that are present in the stones string and return the total count of those characters.

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 letter.
• All the characters of jewels are unique.

My Submission 1 — Using the includes() Method

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */

var numJewelsInStones = function(jewels, stones) {
    let count = 0
    for(let i=0; i < stones.length; i++){
        if(jewels.includes(stones[i])){
            count++
        }
    }
    return count
};

1. Initialize the count variable to store the final count of jewels.
2. Loop through the stones string, and check if each character is present in the jewels string using the includes() method.
3. If it is included, increment the count variable.
4. Finally, return the count variable.

This solution has a time complexity of O(m×n), where m is the length of the stones string and n is the length of the jewels string. This is because the includes() method iterates through the jewels string for each character in stones. If the input size increases, this approach becomes inefficient. We need to optimize the solution to reduce the time complexity.

My Submission 2 — Using the Set() Method (Hash Table)

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    const jewelsMap = new Set(jewels)
    let count = 0
    for(let i=0; i < stones.length; i++){
        if(jewelsMap.has(stones[i])) {
            count++
        }
    }
    return count
};

1. Initialize the count variable to store the final count of jewels.
2. Create a Set from the jewels string. A Set allows for faster lookups because it uses a hash table internally.
3. Loop through the stones string, and check if each character exists in the Set using the has() method.
4. If the character exists, increment the count variable.
5. Finally, return the count variable.

Why Set() is Faster Than includes()?

The includes() method checks for a value by iterating through the jewels string one character at a time. This means the time complexity for each check is O(n), where n is the length of the jewels string.

On the other hand, the Set data structure uses a hash table internally. This allows for constant-time O(1) lookups using the has() method. While creating the Set initially takes O(n) time, subsequent lookups are much faster compared to the includes() method.

-

If you find any mistakes in my post or have a different perspective, feel free to leave a comment below. I always enjoy learning from different viewpoints! 😊 Also, if you liked this post, I'm happy to connect on LinkedIn anytime.