0
\$\begingroup\$

The task

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 functional solution

const findNumberOfJewels = (j,s) =>  [...s].reduce((num, x) => [...j].includes(x) ? num + 1 : num , 0);

console.log(findNumberOfJewels("aA", "aAAbbbb"));

My imperative solution

function findNumberOfJewels2(j,s) {
  let res = 0;
  const set = new Set(j);
  for (const x of s) {
    if (set.has(x)) { ++res; }
  }
  return res;
};

console.log(findNumberOfJewels2("aA", "aAAbbbb"));
\$\endgroup\$
3
\$\begingroup\$

The functional approach is almost certainly faster despite having worse big-O — \$O(j \cdot s)\$ functional vs \$O(j + s)\$ imperative — because linear searches of small arrays are very fast.

You don't need to destructure j and adding a boolean to a number coerces the boolean to 0 or 1.

sum is a better name than num and c is a good name for a character iterator.

const findNumberOfJewels = (j,s) => [...s].reduce( (sum, c) => sum + j.includes(c),  0 );
\$\endgroup\$
  • \$\begingroup\$ +1 Be careful when making assumptions about JS performance.Running both OPs solutions over a wide range of inputs, the functional solution is from 25% -75% the speed fastTime / slowTime of the imperative. Your modified version is a significant improvement over the OP's, under specific circumstances can be much faster then the imp version (also much slower ). But the alloc of [...s] and coercion of j.includes to Number means it will always be slower (by ~10%) than findJ(j,s) {var r=0,i=s.length;while(i--){j.includes(s[i])&&r++}return r} (Note that GC cost of [...s] is not timed) \$\endgroup\$ – Blindman67 Apr 22 at 14:37
  • \$\begingroup\$ Were you able to get those results within the given size constraints? I couldn't find valid inputs that make the imperative version beat a linear search. The whole string sits in L1 cache and I'm skeptical that it's possible for Set's lookup characteristics to repay its setup time. \$\endgroup\$ – Oh My Goodness Apr 22 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.