当前位置：首页 > article >正文

算法题之宝石与石头

article 2024/9/22 18:48:58

宝石与石头

给你一个字符串 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++) { // 遍历stones
    char stone = stones.charAt(i);
    for (int j = 0; j < jewelsLength; j++) { // 遍历jewels
        char 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的全部字符。