算法题之宝石与石头

宝石与石头

给你一个字符串 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 中的所有字符都是 唯一的

解题思路一：暴力

首先我们定义一个变量jewelCount，用来返回找到的宝石数量。

int jewelsCount = 0;

我们分别遍历字符串jewels和stones，然后逐一比较两个字符串中的字符串

int jewelsLength = jewels.length(), stonesLength = stones.length();
for (int i = 0; i < stonesLength; i++) { // 遍历stoneschar stone = stones.charAt(i);for (int j = 0; j < jewelsLength; j++) { // 遍历jewelschar jewel = jewels.charAt(j);if (stone == jewel) {// doSomething}}
}

相同则说明是宝石，所以变量jewelCount加一。

if (stone == jewel) {jewelsCount++;break;
}

遍历完以后，我们返回结果，具体代码如下所示：

class Solution {public int numJewelsInStones(String jewels, String stones) {int jewelsCount = 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++) {char jewel = jewels.charAt(j);if (stone == jewel) {jewelsCount++;break;}}}return jewelsCount;}
}

复杂度分析

时间复杂度： $O(mn)$ ，遍历jewels和stones的时间复杂度分别为 $O(m)$ 和 $O(n)$ ，所以总的时间复杂度为 $O(mn)$ 。
空间复杂度： $O(1)$ ，我们只使用了额外常量的空间。

解题思路二：哈希集合

我们可以用一个哈希集合，来存储jewels里的字符，然后遍历stones的字符，判断是否存在宝石。通过哈希集合的结构，可以降低时间复杂度。

具体代码如下：

class Solution {public int numJewelsInStones(String jewels, String stones) {int jewelsCount = 0;Set<Character> jewelsSet = new HashSet<Character>();int jewelsLength = jewels.length(), stonesLength = stones.length();for (int i = 0; i < jewelsLength; i++) {char jewel = jewels.charAt(i);jewelsSet.add(jewel);}for (int i = 0; i < stonesLength; i++) {char stone = stones.charAt(i);if (jewelsSet.contains(stone)) {jewelsCount++;}}return jewelsCount;}
}

复杂度分析

时间复杂度： $O(m+n)$ ，遍历jewels和stones的时间复杂度分别为 $O(m)$ 和 $O(n)$ ，每次遍历stones，判断哈希集合里是否存在宝石的时间复杂度为 $O(1)$ ，所以总的时间复杂度为 $O(m+n)$ 。
空间复杂度： $O(m)$ ，我们使用了哈希数组存储jewels的全部字符。