给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

 

示例 1：

输入：jewels = "aA", stones = "aAAbbbb"
输出：3

示例 2：

输入：jewels = "z", stones = "ZZ"
输出：0

 

提示：

  • 1 <= jewels.length, stones.length <= 50
  • jewels 和 stones 仅由英文字母组成
  • jewels 中的所有字符都是 唯一的

思路分析

两个字符串比较问题，正常时间复杂度 O()
可以通过hash将复杂度降低到O()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def numJewelsInStones_1(self, jewels: str, stones: str) -> int:
        s = set(list(jewels))
        res = 0
        for x in stones:
            if x in s:
                res+=1
        return res

    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        # 位运算
        mask = 0
        for x in jewels:
            mask |= 1 << (ord(x) & 63)
        res = 0
        for x in stones:
            res += (mask >> (ord(x)&63)) & 1
        return res

官解

O()

1
2
3
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        return sum(s in jewels for s in stones)

O()

1
2
3
4
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewelsSet = set(jewels)
        return sum(s in jewelsSet for s in stones)

位运算-灵神

思路分析

本质还是hash，把哈希表通过位运算进行状态压缩
观察 ASCII 表，可以发现：

  • 大写字母二进制的低 6 位是从 000001 开始的（对应大写字母 A），一直到 011010（对应大写字母 Z）。
  • 小写字母二进制的低 6 位是从 100001 开始的（对应小写字母 a），一直到 111010（对应小写字母 z），即十进制的 58。
    ABCDEFGHIJKLMNOPQRSTUVWXYZ 1 - 26
    abcdefghijklmnopqrstuvwxyz 33 - 58
    所以取字符的的低 6 位，就可以把不同的大小写字母映射到不同的数字上。

所以，可以用一个 64 位整数 mask 来代替哈希表/布尔数组，压缩存储 jewels 中的字母。然后遍历 stones，判断每个字母是否在 mask 中。

如何用代码实现？我系统整理了位运算的相关知识，请看 从集合论到位运算，常见位运算技巧分类总结！

1
2
3
4
5
6
7
8
9
10
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        # 位运算
        mask = 0
        for x in jewels:
            mask |= 1 << (ord(x) & 63)
        res = 0
        for x in stones:
            res += (mask >> (ord(x)&63)) & 1
        return res