文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法一
• • 思路和算法
  • 代码
  • 复杂度分析
• 解法二
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：宝石与石头

出处：771. 宝石与石头

难度

2 级

题目描述

要求

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

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

示例

示例 1：

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

示例 2：

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

数据范围

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

解法一

思路和算法

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

最直观的做法是，遍历 stones\textit{stones}stones 中的每个字符，对于每个字符，遍历 jewels\textit{jewels}jewels 中的每个字符，如果发现 jewels\textit{jewels}jewels 中存在一个字符和 stones\textit{stones}stones 的当前字符相同，则 stones\textit{stones}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;}
}

复杂度分析

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

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

解法二

思路和算法

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

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

代码

class Solution {public int numJewelsInStones(String jewels, String stones) {int count = 0;Set jewelsSet = new HashSet();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;}
}

复杂度分析

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

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