LeetCode 771.Jewels and Stones

The world is a fine place, and worth fighting for.

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.

直接想到的方案是这样的:

class Solution {
    public int numJewelsInStones(String J, String S) {
        char[] jChar = J.toCharArray();
        char[] sChar = S.toCharArray();
        int num = 0;
        for(int i =0; i< jChar.length;i++){
            for(int j=0;j<sChar.length;j++){
                if(jChar[i] == sChar[j]){
                    num++;
                }
            }
        }
        return num;
    }
}

虽然通过了网站的测试用例,但是我加了一个测试用例，发现了这个解法是有问题的，例如输入“aAa”和”aAAbbbb”,结果并不是3.

在讨论区看到了一个比较有趣的解法:

class Solution {
    public int numJewelsInStones(String J, String S) {
        int[] map = new int[58];
        int result = 0;
        for(char c:S.toCharArray()){
            map[c-'A']++;
        }
        for(char c:J.toCharArray()){
            result += map[c-'A'];
        }
        return result;
    }
}

但是这个解法依然没有解决J字符串包含重复字符的问题

最后看到了一个利用HashSet来解决的:

class Solution {
    public int numJewelsInStones(String J, String S) {
        Set<Character> set = new HashSet<>();
        for (Character c: J.toCharArray()) {
            set.add(c);
        }
        int count = 0;
        for (Character c: S.toCharArray()) {
            if (set.contains(c)) {
                count++;
            }
        }
        return count;
    }
}