771. Jewels and Stones

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 <= 50
jewels 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(|\Sigma|)\), where \(m\) and \(n\) are the lengths of the strings \(jewels\) and \(stones\) respectively, and \(\Sigma\) is the character set, which in this problem is the set of all uppercase and lowercase English letters.

Python3JavaC++GoTypeScriptRustJavaScriptC

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        s = set(jewels)
        return sum(c in s for c in stones)

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;
    }
}

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;
    }
};

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
}

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;
}

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
    }
}

/**
 * @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);
};

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;
}

771. Jewels and Stones

Description

Solutions

Solution 1: Hash Table or Array

Comments