[Algorithm] . Jewels and Stones

Problem Description

Given two strings: jewels represents the gem type, and stones represents the stone you have. Each character in stones represents a certain type of stone you own. You need to calculate how many of the stones you own are also gems.

Letters are case-sensitive, so "a" and "A" represent different types of stones.

Key to the problem

Finds the characters in the jewels string that are present in the stones string and returns the total number of these characters.

Example 1

<code>输入：jewels = "aA", stones = "aAAbbbb"
输出：3</code>

Example 2

<code>输入：jewels = "z", stones = "ZZ"
输出：0</code>

Constraints

• 1 ≤ jewels.length, stones.length ≤ 50
• jewels and stones contain only English letters.
All characters in
• jewels are unique.

Option 1: Use includes() method

<code class="language-javascript">/**
 * @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;
};</code>

Steps:

1. Initialization counter count is used to store the total number of gems.
2. Loop through the stones string, using the includes() method to check whether each character is in the jewels string.
3. Increments count if included.
4. Finally returns count.

The time complexity of this method is O(m*n), where m is the length of the stones string and n is the length of the jewels string. Because the includes() method will traverse the jewels string each character. This approach is inefficient when the input size increases. We need to optimize the solution to reduce time complexity.

Option 2: Use the Set() method (hash table)

<code class="language-javascript">/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    const jewelsSet = new Set(jewels);
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (jewelsSet.has(stones[i])) {
            count++;
        }
    }
    return count;
};</code>

Steps:

1. Initialization counter count is used to store the total number of gems.
2. Create a jewels using the Set string. Set Uses a hash table, allowing faster lookups.
3. Loop through the stones string, using the has() method to check whether each character is in a Set.
4. Increments count if present.
5. Finally returns count.

Why is Set() faster than includes()?

The

includes() method checks the value by iterating over the jewels string character by character, with a time complexity of O(n) for each check, where n is the length of the jewels string.

And the Set data structure uses a hash table internally, allowing constant time O(1) lookups using the has() method. While creating Set initially takes O(n) time, subsequent lookups are much faster than the includes() method.

If I have any errors or you have different views, please leave a message at any time. I am always happy to learn from different perspectives! ? If you like this article, please contact me on LinkedIn at any time.

The above is the detailed content of [Algorithm] . Jewels and Stones. For more information, please follow other related articles on the PHP Chinese website!