LeetCode 771. 宝石与石头

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 中的字符不重复。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jewels-and-stones/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 1. 迭代法

思路：分别遍历字符串 J ，S， 使用 charAt() 判断如果有相同元素则 num++ 即可

public static int numJewelsInStones(String J, String S) {
        if (J.length() == 0 || S.length() == 0) return 0;
        int num = 0;
        for (int i = 0; i < S.length(); i++) {
            for (int j = 0; j < J.length(); j++) {
                if (S.charAt(i) == J.charAt(j)) {
                    num++;
                }
            }
        }
        return num;
    }

复杂度分析：

• 时间复杂度：O(m * n): m、n 分别代表字符串的长度

• 空间复杂度：O(1), 只需要常数级别的空间复杂度

• 2. 优化方法1

思路：使用 indexOf()) 降低时间复杂度

1. 遍历字符串 S，依次取出每个元素；

• 2. 使用 indexOf() 判断 J 中是否包含该元素

public static int numJewelsInStones(String J, String S) {
        if (J.length() == 0 || S.length() == 0) return 0;
        int num = 0;
        for (int i = 0; i < S.length(); i++) {
            String str = S.substring(i, i + 1);
            if (J.indexOf(str) != -1) num++;
        }
        return num;
    }

复杂度分析：

• 时间复杂度：O(n), n 为字符串 S 的长度

• 空间复杂度：O(1)

• 3.set集合法

思路：使用 set 集合以空间换时间

1. 将字符串依次放入 set 集合中
2. 遍历字符串 S，判断 set 中是否包含相同元素

public static int numJewelsInStones(String J, String S) {
        if (J.length() == 0 || S.length() == 0) return 0;
        Set<Character> set = new TreeSet<>();
        int num = 0;
        for (int i = 0; i < J.length(); i++) {
            set.add(J.charAt(i));
        }
        for (int j = 0; j < S.length(); j++) {
            if (set.contains(S.charAt(j))) num++;
        }
        return num;
    }

复杂度分析：

• 时间复杂度：O(m + n)

• 空间复杂度：O(m), m 为字符串 J 的长度

• 测试用例

public static void main(String[] args) {
         String J = "aA";
         String S = "aAAbbbb";
         System.out.println(J);
         System.out.println(S);
         System.out.println("宝石与石头：" + numJewelsInStones(J, S));
    }

• 结果

aA
aAAbbbb
宝石与石头：3

• 源码

• 我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github