Open rmorabia opened 5 years ago
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).
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.
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)
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:
Example 2: