[Leetcode] 771. Jewels and Stones

[rmorabia]

Link: https://leetcode.com/problems/jewels-and-stones/

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:

Example 2:

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

[rmorabia]

var numJewelsInStones = function (J, S) {
  let count = 0
  for (let i = 0; i < S.length; i++) {
    if (J.includes(i)) {
      count++
    }
  }
  return count
}

This is O(n^2).

[rmorabia]

var numJewelsInStones = function (J, S) {
  // Convert J to object
  // No ordering issues like arrays
  // KEYS ARE UNIQUE, values are not!
  const obj = {}
  for (let i = 0; i < J.length; i++) {
    obj[J[i]] = 1
  }

  // For every value in S, if the key in object exists, bam slam.
  let counter = 0
  for (let i = 0; i < S.length; i++) {
    if (obj[S[i]]) {
    counter++
    }
  }
  return counter
}

This is O(n). Accessing the object is constant time.

[cs-cordero]

Python Solution.

Time: O(J+S)
Space: O(J)

    def numJewelsInStones(self, J: str, S: str) -> int:
        jewels = set(J)
        return sum(stone in jewels for stone in S)