Description
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.
Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: jewels = "aA", stones = "aAAbbbb"
Output: 3
Example 2:
Input: jewels = "z", stones = "ZZ"
Output: 0
Constraints:
1 <= jewels.length, stones.length <= 50jewels and stones consist of only English letters.- All the characters of
jewels are unique.
Solutions
Solution 1: Hash Table or Array
We can first use a hash table or array s to record all types of jewels. Then traverse all the stones, and if the current stone is a jewel, increment the answer by one.
Time complexity is O(m+n), and space complexity is O(|Σ|), where m and n are the lengths of the strings jewels and stones respectively, and Σ is the character set, which in this problem is the set of all uppercase and lowercase English letters.
PythonJavaC++GoTypeScriptRustJavaScriptC
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
s = set(jewels)
return sum(c in s for c in stones)(code-box)
class Solution {
public int numJewelsInStones(String jewels, String stones) {
int[] s = new int[128];
for (char c : jewels.toCharArray()) {
s[c] = 1;
}
int ans = 0;
for (char c : stones.toCharArray()) {
ans += s[c];
}
return ans;
}
}(code-box)
class Solution {
public:
int numJewelsInStones(string jewels, string stones) {
int s[128] = {0};
for (char c : jewels) {
s[c] = 1;
}
int ans = 0;
for (char c : stones) {
ans += s[c];
}
return ans;
}
};(code-box)
func numJewelsInStones(jewels string, stones string) (ans int) {
s := [128]int{}
for _, c := range jewels {
s[c] = 1
}
for _, c := range stones {
ans += s[c]
}
return
}(code-box)
function numJewelsInStones(jewels: string, stones: string): number {
const s = new Set([...jewels]);
let ans = 0;
for (const c of stones) {
s.has(c) && ans++;
}
return ans;
}(code-box)
use std::collections::HashSet;
impl Solution {
pub fn num_jewels_in_stones(jewels: String, stones: String) -> i32 {
let mut s = jewels.as_bytes().iter().collect::<HashSet<&u8>>();
let mut ans = 0;
for c in stones.as_bytes() {
if s.contains(c) {
ans += 1;
}
}
ans
}
}(code-box)
/**
* @param {string} jewels
* @param {string} stones
* @return {number}
*/
var numJewelsInStones = function (jewels, stones) {
const s = new Set(jewels.split(''));
return stones.split('').reduce((prev, val) => prev + s.has(val), 0);
};(code-box)
int numJewelsInStones(char* jewels, char* stones) {
int set[128] = {0};
for (int i = 0; jewels[i]; i++) {
set[jewels[i]] = 1;
}
int ans = 0;
for (int i = 0; stones[i]; i++) {
set[stones[i]] && ans++;
}
return ans;
}(code-box)
