Question

771. 宝石与石头

English Version

题目描述

 给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

 

示例 1：

输入：jewels = "aA", stones = "aAAbbbb"
输出：3

示例 2：

输入：jewels = "z", stones = "ZZ"
输出：0

 

提示：

• 1 <= jewels.length, stones.length <= 50
• jewels 和 stones 仅由英文字母组成
• jewels 中的所有字符都是 唯一的

解法

方法一：哈希表或数组

我们可以先用一个哈希表或数组 $s$ 记录所有宝石的类型。然后遍历所有石头，如果当前石头是宝石，就将答案加一。

时间复杂度 $O(m+n)$，空间复杂度 $O(|\Sigma|)$，其中 $m$ 和 $n$ 分别是字符串 $jewels$ 和 $stones$ 的长度，而 $\Sigma$ 是字符集，本题中字符集为所有大小写英文字母的集合。

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 set = jewels.as_bytes().iter().collect::<HashSet<&u8>>();
    let mut ans = 0;
    for c in stones.as_bytes() {
      if set.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;
}