Leetcode-771-宝石与石头

题目描述

• 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

• J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此”a”和”A”是不同类型的石头。

示例 1:

输入: J = "aA", S = "aAAbbbb"
输出: 3

示例 2:

输入: J = "z", S = "ZZ"
输出: 0

注意:

• S 和 J 最多含有50个字母。
• J 中的字符不重复。

思路 1： HashSet

• 标签：字符串
• 首先对J进行遍历，将字符分别存到HashSet中，以便之后遍历S的时候查找
• 遍历S，并将每个字符与HashSet中的进行比对，如果存在，则结果res++，遍历结束，返回res

class Solution {
    public int numJewelsInStones(String J, String S) {
        Set<Character> set = new HashSet<>();

        // 1. 把J中字符都加入到hashset中
        for(int i = 0;i < J.length();i++){
            set.add(J.charAt(i));
        }

        int res = 0;

        // 2.判断 S中是否有对应的字符
        for(int i = 0;i < S.length();i++){
            if(set.contains(S.charAt(i))){
                res++;
            }
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：O(m+n)，m为J的长度，n为S的长度
• 空间复杂度： O(m) 需要把J中字符都加入到hashset中

思路2：暴力求解

• 暴力法的思路很直观，遍历字符串 SS，对于 SS 中的每个字符，遍历一次字符串 J，如果其和 J中的某一个字符相同，则是宝石。

class Solution {
    public int numJewelsInStones(String J, String S) {
        int count = 0;
        int len1 = J.length();
        int len2 = S.length();

        for(int i = 0; i < len2;++i){
            char curr = S.charAt(i);
            for(int j = 0; j < len1;++j){
                char jewel = J.charAt(j);
                if(curr == jewel){
                    count++;
                    break;
                }
            }
        }

        return count;
    }
}

复杂度分析

• 时间复杂度：O(mn)，其中 mm 是字符串 J的长度，n 是字符串 S的长度。遍历字符串 S 的时间复杂度是 O(n)，对于 SS 中的每个字符，需要遍历字符串 J判断是否是宝石，时间复杂度是 O(m)，因此总时间复杂度是 O(mn)。
• 空间复杂度：O(1)。只需要维护常量的额外空间。

打赏