Jewels and Stones#

Given a string J representing the types of stones that are jewels, and a string S representing the stones you have. You want to know how many of the stones you have are also jewels.

The letters in J are distinct, and all characters in J and S are letters. Letters are case sensitive, so a and A are considered different types of stones.

Example#

Solution#

/**
 * @param {string} J
 * @param {string} S
 * @return {number}
 */
var numJewelsInStones = function(J, S) {
    var hashTable = {};
    var target = 0;
    Array.prototype.forEach.call(J, v => hashTable[v] = 1);
    Array.prototype.forEach.call(S, v => {
        if(hashTable[v]) ++target;
    })
    return target;
};

Idea#

If we directly use a brute-force traversal, the time complexity will be relatively high. By using a hash table to record the types of jewels, and then traversing the string to find the jewels we have, it can be achieved. First, define HashTable to record the types of jewels. Then define the target count to start at 0. Next, iterate through the strings. For convenience, directly call the forEach method of the Array prototype, and use the arrow function. Assign the value of the type of jewel to 1. Similarly, traverse the string to determine if the value is defined as a jewel in the hash table. If it is, increase the target count ++. Finally, return the target count.

Daily Exercise#

Reference#