LC.P771[宝石与石头]

方法一：哈希表

java
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); ++i) {
            set.add(jewels.charAt(i));
        }
        int ans = 0;
        for (int i = 0; i < stones.length(); ++i) {
            if (set.contains(stones.charAt(i))) ++ans;
        }
        return ans;
    }
}
  • 时间复杂度：O(m+n)
  • 空间复杂度：O(C)，其中C为所有大小写英文字母的集合

方法二：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int[] s = new int[128];
        for (int i = 0; i < jewels.length(); ++i) {
            s[jewels.charAt(i)] = 1;
        }
        int ans = 0;
        for (int i = 0; i < stones.length(); ++i) {
            ans += s[stones.charAt(i)];
        }
        return ans;
    }
}
  • 时间复杂度：O(m+n)
  • 空间复杂度：O(C)，其中C为所有大小写英文字母的集合