哈希表题目：宝石与石头

题目

标题和出处

标题：宝石与石头

出处：771. 宝石与石头

难度

2 级

题目描述

要求

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

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

示例

示例 1：

输入：$\text{jewels = "aA", stones = "aAAbbbb"}$
输出：$\text{3}$

示例 2：

输入：$\text{jewels = "z", stones = "ZZ"}$
输出：$\text{0}$

数据范围

• $\text{1}\le \text{jewels.length, stones.length}\le \text{50}$
• $\text{jewels}$ 和 $\text{stones}$ 仅由英语字母组成
• $\text{jewels}$ 中的所有字符都是唯一的

解法一

思路和算法

为了计算石头中有多少是宝石，需要判断每个石头是不是宝石，即判断字符串 $\text{stones}$ 中的每个字符是否在字符串 $\text{jewels}$ 中出现。

最直观的做法是，遍历 $\text{stones}$ 中的每个字符，对于每个字符，遍历 $\text{jewels}$ 中的每个字符，如果发现 $\text{jewels}$ 中存在一个字符和 $\text{stones}$ 的当前字符相同，则 $\text{stones}$ 的当前字符是宝石。遍历结束之后即可得到石头中有多少是宝石。

代码

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        int jewelsLength = jewels.length(), stonesLength = stones.length();
        for (int i = 0; i < stonesLength; i++) {
            char stone = stones.charAt(i);
            for (int j = 0; j < jewelsLength; j++) {
                if (stone == jewels.charAt(j)) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

• 时间复杂度：$O(mn)$，其中 $m$ 是字符串 $\text{jewels}$ 的长度，$n$ 是字符串 $\text{stones}$ 的长度。需要遍历 $n$ 个石头，对于每个石头，需要 $O(m)$ 的时间判断该石头是不是宝石，因此总时间复杂度是 $O(mn)$。

• 空间复杂度：$O(1)$。

解法二

思路和算法

解法一中，判断每个石头是不是宝石需要 $O(m)$ 的时间。如果使用哈希集合存储宝石，则判断每个石头是不是宝石只需要判断该石头是否在哈希集合中，可以将时间复杂度从 $O(m)$ 降低到 $O(1)$。

首先遍历 $\text{jewels}$ 中的每个字符并将字符加入哈希集合，然后遍历 $\text{stones}$ 中的每个字符，对于 $\text{stones}$ 中的每个字符，判断该字符是否在哈希集合中，即可知道该字符是不是宝石。遍历结束之后即可得到石头中有多少是宝石。

代码

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        Set<Character> jewelsSet = new HashSet<Character>();
        int jewelsLength = jewels.length(), stonesLength = stones.length();
        for (int i = 0; i < jewelsLength; i++) {
            jewelsSet.add(jewels.charAt(i));
        }
        for (int i = 0; i < stonesLength; i++) {
            if (jewelsSet.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

• 时间复杂度：$O(m+n)$，其中 $m$ 是字符串 $\text{jewels}$ 的长度，$n$ 是字符串 $\text{stones}$ 的长度。首先遍历字符串 $\text{jewels}$ 并将 $\text{jewels}$ 的每个字符加入哈希集合，需要 $O(m)$ 的时间，然后遍历字符串 $\text{stones}$，对于字符串 $\text{stones}$ 中的每个字符需要 $O(1)$ 的时间判断是不是宝石，共需要 $O(n)$ 的时间计算有多少石头是宝石，因此总时间复杂度是 $O(m+n)$。

• 空间复杂度：$O(m)$，其中 $m$ 是字符串 $\text{jewels}$ 的长度。需要使用哈希集合存储字符串 $\text{jewels}$ 中的全部字符，由于 $\text{jewels}$ 中的字符都不重复，因此哈希集合中的元素个数是 $m$。