LeetCode 771. Jewels and Stones

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.

My Solution

My approach was to convert the string to character arrays. Then use a built in filter method to count the intersection of each character element. It’s a very similar approach to how I would do it in C# with linq.

The Array filter method is O(n) and that is wrapped inside another for loop so the time complexity is O(n^2).

Time: 11.30

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    let j = Array.from(jewels);
    let s = Array.from(stones);
    let count = 0;
    for (index in j)
        {
            count += s.filter(stone => stone == j[index]).length;
        }
    return count;
};

A Nice Solution

This solution is shorter and uses the Set data structure. Set has is O(1) since it is based on a keyed collection. For this simple calculation the time complexity of array reduce is 0(n) making the whole solution O(n). (Creating a set from a list is also linear time complexity).

Some notes on what I learned.

1. Array reduce() iterates over the array making a calculation or operation. The result is cummulative across all elements.

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    const jset = new Set(jewels)
    return stones.split('').reduce((res, s) => res + jset.has(s), 0)
};