771. Jewels and Stones

Description

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} j
 * @param {string} s
 * @return {number}
 */
let numJewelsInStones = function(j, s) {
  let jewels = j.split("");
  let jewelCount = 0;
  let stones = s.split("");

  for (jewel of jewels) {
    //for efficiency purposes only
    if (stones.indexOf(jewel) === -1) {
      continue;
    }
    for (stone of stones) {
      if (jewel === stone) {
        jewelCount++;
      }
    }
  }

  return jewelCount;
};

Analysis

This was a simple problem. First we split the jewel and stone strings into arrays. Then we iterate over each jewel and count the number of times it occurs in the stone array. The running time would be O(js) where j is the length of the jewel string and s is the length of the stone string.

If we check if the stone string contains the jewel before iterating over it, we improve the running time slightly. With this optimization, the time is 56ms versus 60ms without. It's still going to be O(js) though. I'm trying to think of an even better way to do this problem but I think this might be the simplest way.