06 Jewels and Stones

题目

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so “a” is considered a different type of stone from “A”.

Example 1:

Input: J = “aA”, S = “aAAbbbb” Output: 3

Example 2:

Input: J = “z”, S = “ZZ” Output: 0

Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

分析

题意：给出一串字符串J表示宝石，一串S表示你拥有的石头，从S中查看你拥有多少个宝石，大小写敏感。

最暴力的解法就是两层循环，将J中的字符与S中的字符一一比对。

class Solution {
    public int numJewelsInStones(String J, String S) {
        int sum=0;
        for(char j:J.toCharArray()){
            for(char s:S.toCharArray()){
                if(j==s)
                    sum++;
            }
        }
        return sum;
    }
}

java字符串不能直接遍历，需要转成字符数组

但是显然这种方法是不可取的，成本太高。

没想到其他方法，看了下评论区

最装逼的一行java代码

利用正则表达式的特性，但是速度太慢了，空间复杂度也不见得减小。

return S.replaceAll("[^" + J + "]", "").length();

降低时间复杂度

如果数据够大，下面这个算法能够明显降低耗时。

思路：

• 将宝石放入集合（无序、互异、确定）中；
• 如果宝石集合包含S中的石头，则计数加一

关键就在于将宝石J放在了一个具有“对外分辨”能力的盒子里。

class Solution {
    public int numJewelsInStones(String J, String S) {
        int res = 0;
        Set setJ = new HashSet();
        for (char j: J.toCharArray())
            setJ.add(j);
        for (char s: S.toCharArray())
            if (setJ.contains(s)) res++;
        return res;
    }
}

最快的方法

class Solution {
    public int numJewelsInStones(String J, String S) {
       int res=0;
       for(char c : S.toCharArray()){
           if(J.indexOf(c) != -1){
               res++;
           }
       }
       return res;
    }
}

思路一样：遍历石头，如果存在宝石，则计数加一。

这道算法题更多的是考察工具的使用，解题思想基本一致。

扩展

如果本题改为大数据题，假设石头S的个数是以亿为单位，从中找出宝石的个数，可以采取以下思路。

• 将石头S映射到int[] stones[52]中，stones中的数据表示该下标的对应字母拥有个数（下标映射集合a~z,A~Z，分别对应到0~25,26~51。）。 如：stones[2]=300，表示字母“c”的个数有300个。
• 将宝石J映射到int[] jewels[52]中，jewels[n]=1表示对应的字母为宝石
• sum(stones[jewels[i]])，其中 i∈[0,25]，jewels[i]=1

时间复杂度O(n)；