题目链接

宝石计数

题目描述

给定一个字符串 jewels 代表宝石的类型（jewels 中的字符不重复），再给定一个字符串 stones 代表你拥有的石头。你需要计算出 stones 中有多少个字符是宝石。

  • 字符区分大小写，"a" 和 "A" 是不同类型的石头。
  • jewels 的长度范围是 [1, 50]。
  • stones 的长度范围是 [1, 50]。

示例: 输入: jewels = "aA", stones = "aAAbbbb" 输出: 3 解释: stones 中有 'a', 'A', 'A' 三个宝石。

解题思路

这道题是核心代码模式，我们需要实现一个函数，统计一个字符串 (stones) 中有多少字符也存在于另一个字符串 (jewels) 中。

1. 低效解法：暴力搜索 最直接的想法是遍历 stones 字符串中的每一个字符，对于每个字符，再去遍历一遍 jewels 字符串，看它是否存在。这是一个嵌套循环，时间复杂度为 ，其中 代表字符串S的长度。虽然对于本题给定的数据范围（长度最大为50）可以通过，但这不是最优解。

2. 高效解法：哈希集合 为了优化查找效率，我们可以利用哈希集合（Set）提供的近乎 的查找速度。

  1. 构建宝石集合：首先，遍历 jewels 字符串，将其中的每一个字符都添加到一个哈希集合中。这样我们就拥有了一个所有宝石类型的快速查找表。
  2. 遍历并计数：然后，遍历 stones 字符串。对于 stones 中的每一个字符，我们去哈希集合中查询它是否存在。
  3. 如果存在，则将我们的计数器加一。
  4. 遍历结束后，返回最终的计数值。

这个方法的总时间复杂度主要由两个独立的遍历决定，为 ，比暴力解法高效得多。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param jewels string字符串 
     * @param stones string字符串 
     * @return int整型
     */
    int numJewelsInStones(string jewels, string stones) {
        set<char> jewel_set(jewels.begin(), jewels.end());
        int count = 0;
        for (char stone : stones) {
            if (jewel_set.count(stone)) {
                count++;
            }
        }
        return count;
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param jewels string字符串 
     * @param stones string字符串 
     * @return int整型
     */
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> jewelSet = new HashSet<>();
        for (char j : jewels.toCharArray()) {
            jewelSet.add(j);
        }
        
        int count = 0;
        for (char s : stones.toCharArray()) {
            if (jewelSet.contains(s)) {
                count++;
            }
        }
        
        return count;
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param jewels string字符串 
# @param stones string字符串 
# @return int整型
#
class Solution:
    def numJewelsInStones(self , jewels: str, stones: str) -> int:
        jewel_set = set(jewels)
        # 使用生成器表达式和sum()函数，这是一种更Pythonic的写法
        return sum(s in jewel_set for s in stones)

算法及复杂度

  • 算法: 哈希集合/有序集合
  • 时间复杂度:
    • C++: 。构建 std::set 需要 ，后续遍历 stones 每次查询需要 。
    • Java/Python: 。构建哈希集合需要 ，遍历 stones 每次查询的平均时间是 。
  • 空间复杂度: ，用于存储宝石集合。 和 分别是 jewels 和 stones 的长度。